HDU4057 Rescue the Rabbit(AC 로봇 + Shape DP)

제목은 대략 몇 개의 DNA 부분과 그들 각자의 값을 주는 것이다. 만약에 한 DNA가 어떤 부분을 포함한다면 그 가치는 이 부분의 값을 더하고 여러 개의 같은 DNA 부분을 포함하는 것도 한 번만 더한다. 길이 l의 DNA가 가능한 최대 가치를 묻는다.
HDU2825와 대동소이하다.

dp[i][j][S]는 길이 i(자동기 이동 i보), 접미사 상태가 자동기 제j의 결점, 포함된 DNA 세그먼트가 집합 S의 DNA 최대 가치

를 나타낸다.

dp[0][0][0]=0

저는 모든 사람을 위해 이동합니다. dp[i][j][S]에서 ATCG 네 방향으로 dp[i+1][j'][S']

를 업데이트합니다.

주의해야 할 것은 스크롤 그룹을 사용해야 한다. 그렇지 않으면 백조 그룹을 열어야 한다.

스크롤 그룹으로 초기화에 주의해야 합니다.

전이 과정의 일부 계산은 미리 처리할 수 있고 수조에 존재한다. 미리 처리하지 않아도 TLE를 할 수 없지만 제목 시간은 10000ms를 주었다.

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 using namespace std;
 5 #define INF (1<<30)
 6 int tn,ch[1111][4],fail[1111],flag[1111];
 7 int idx[128];
 8 void insert(char *s,int k){
 9     int x=0;
10     for(int i=0; s[i]; ++i){
11         int y=idx[s[i]];
12         if(ch[x][y]==0) ch[x][y]=++tn;
13         x=ch[x][y];
14     }
15     flag[x]|=1<<k;
16 }
17 void init(){
18     memset(fail,0,sizeof(fail));
19     queue<int> que;
20     for(int i=0; i<4; ++i){
21         if(ch[0][i]) que.push(ch[0][i]);
22     }
23     while(!que.empty()){
24         int x=que.front(); que.pop();
25         for(int i=0; i<4; ++i){
26             if(ch[x][i]) que.push(ch[x][i]),fail[ch[x][i]]=ch[fail[x]][i],flag[ch[x][i]]|=flag[ch[fail[x]][i]];
27             else ch[x][i]=ch[fail[x]][i];
28         }
29     }
30 }
31 int d[2][1111][1<<10],VAL[1<<10];
32 int main(){
33     idx['A']=0; idx['G']=1; idx['T']=2; idx['C']=3;
34     int m,n,a;
35     char str[111];
36     int val[11];
37     while(~scanf("%d%d",&m,&n)){
38         tn=0;
39         memset(ch,0,sizeof(ch));
40         memset(flag,0,sizeof(flag));
41         for(int i=0; i<m; ++i){
42             scanf("%s%d",str,val+i);
43             if(strlen(str)>100) continue;
44             insert(str,i);
45         }
46         for(int i=1; i<(1<<m); ++i){
47             for(int j=0; j<m; ++j){
48                 if((i>>j)&1) VAL[i]=VAL[i^(1<<j)]+val[j];
49             }
50         }
51         init();
52         for(int j=0; j<=tn; ++j){
53             for(int k=0; k<(1<<m); ++k) d[0][j][k]=-INF;
54         }
55         d[0][0][0]=0;
56         for(int i=0; i<n; ++i){
57             int x=i&1;
58             for(int j=0; j<=tn; ++j){
59                 for(int k=0; k<(1<<m); ++k) d[x^1][j][k]=-INF;
60             }
61             for(int j=0; j<=tn; ++j){
62                 for(int k=0; k<(1<<m); ++k){
63                     if(d[x][j][k]==-INF) continue;
64                     for(int y=0; y<4; ++y){
65                         d[x^1][ch[j][y]][k|flag[ch[j][y]]]=max(d[x^1][ch[j][y]][k|flag[ch[j][y]]],d[x][j][k]+VAL[k^(k|flag[ch[j][y]])]);
66                     }
67                 }
68             }
69         }
70         int res=-INF;
71         for(int i=0; i<=tn; ++i){
72             for(int j=0; j<(1<<m); ++j) res=max(res,d[n&1][i][j]);
73         }
74         if(res<0) puts("No Rabbit after 2012!");
75         else printf("%d
",res);
76     }
77     return 0;
78 }