HDU2296 링(AC 로봇 + DP)

제목은 몇 개의 가치 있는 단어를 주는 것이다.한 문자열의 가치는 각 단어가 그 안에 나타난 횟수 * 단어의 가치와 길이가 n을 초과하지 않는 가장 큰 가치를 묻는 문자열은 무엇입니까?
여전히 입문한 AC 자동기 + DP 문제입니다.다른 것은 이 문제는 구체적인 방안을 출력하고 각 상태의 가장 좋은 상황을 기록하는 문자열을 추가하면 된다는 것이다.
또한 제목의 사전 순서는 길이를 먼저 고려한 다음에 모든 단어를 고려한다.특히 디스커스를 보고 알 수 있는 매우 구덩이가 하나 있다. 단어 A는 단어 B를 포함하고 있다면 단어 A만 계산하고 단어 B는 계산하지 않는다.

dp[i][j]는 길이 i(자동기에서 k걸음 이동) 접미사 상태가 자동기 j개 결점의 문자열의 최대 가치임을 나타낸다

dp[0][0]=0

나는 사람마다 dp[i][j]가 26개 자모로 dp[i'][j']

로 옮겼다

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