POJ3395 Trie|DP

3395 -- Shift Cipher

这题也不难，可能是因为数据范围没有明确，才会出现这么低的AC比例，我RE了三次才设定了一个比较合适的范围，trie节点个数200000就足够了

题意主要是

1. 给定一个字符串，分割成字典中单词，并且最小化单词书目，并且分割后的单词的平均长度不能小于3， 还需要满足分割后的单词不能有连续的两个长度为1的单词

2. 字符串是经过shift cipher的，需要解码后再分割，只有26个可能所以可以直接遍历

思路

简单的动态规划：dp(i) 表示从第i个字符开始分割最少可以分割成多少个单词， dp2(i)表示从第i个字符开始第一个单词的长度至少是2，最少可以分割成多少个单词， 假设无效分割的分割数为inf，那么

dp(i) = min(m(i, i)+dp2(i+1), m(i, j)+dp(j+1))

dp2(i) = min(m(i, j)+dp(j+1))

j的范围(i, n); 如果i, j之间的字符串可以构成有效的单词则m(i,j)=1否则m(i,j)=inf;

实现

Trie数据结构

void assert(int *p) { *p=0; }
#define MAXN 200000
int trie[MAXN][26], tc;
char mk[MAXN];
int alloc() {
    if (tc>=MAXN) { assert(0); }
    int i; for (i=0; i<26; i++) trie[tc][i]=-1; mk[tc]=0;
    return tc++;
}

构建Trie

    tc=0; alloc();
    while(1) {
        ib[0]=0; fgets(ib, sizeof(ib), stdin);
        i=0; while(ib[i]>='a'&&ib[i]<='z') i++;
        if (ib[i]==0||ib[i]=='\r'||ib[i]=='\n') {
            if (i==0) break; ib[i]=0;
            r=0; for (j=0; j<i; j++) {
                c=ib[j]-'a';
                if (trie[r][c]==-1) trie[r][c]=alloc();
                r=trie[r][c];
            } mk[r]=1;
        }
    }

遍历26个key，每个key做一次DP

        for (k=0; k<26; k++) {
            for (i=0; i<n; i++) { c=ib[i]-'a'; c-=k; if (c<0) c+=26; ss[i]=c; }
            dp[n]=0; dp2[n]=0;
            for (i=n-1; i>=0; i--) {
                r=0; rr=-1; rr2=-1; for (j=i; j<n; j++) {
                    c=ss[j]; if (trie[r][c]==-1) break;
                    r=trie[r][c];
                    if (mk[r]) {
                        if (j==i) {
                            t=dp2[j+1]; if (t>=0) {
                                t+=1; if (rr<0||rr>t) {
                                    rr=t;
                                    dpi[i]=j+1-i;
                                }
                            }
                        } else {
                            t=dp[j+1]; if (t>=0) {
                                t+=1; if (rr<0||rr>t) {
                                    rr=t;
                                    dpi[i]=j+1-i;
                                }
                                if (rr2<0||rr2>t) {
                                    rr2=t;
                                    dpi2[i]=j+1-i;
                                }
                            }
                        }
                    }
                }
                dp[i]=rr; dp2[i]=rr2;
            }
            r = dp[0];
            if (r<=0 || (n+r-1)/r<=2) continue;
            if (rc==0||rc>r) {
                rk=k; rc=r;
                j=0;
                i=0; h=-1; while(i<n) {
                   if (h==1) h=dpi2[i];
                   else h=dpi[i];
                   for (rr=0; rr<h; rr++) ob[j++]=ss[i++]+'a'; ob[j++]=' ';
                }
                ob[j-1]=0;
            }
        }