【題目大意】

給你個(gè)模式串（每個(gè)長(zhǎng)度≤15，1≤N≤20），串中只含有三種字母。求一長(zhǎng)度為K（1≤K≤1000）的字符串，使得匹配數(shù)最大（重復(fù)匹配計(jì)多次），輸出最大值。

【解題思路】

W老師給的題，然而我不會(huì)做。嗚嗚嗚謝謝丁爺爺教我做題，神犇丁爺爺%%%。下面都是丁爺爺?shù)脑?#xff0c;和我沒有關(guān)系。然而丁爺爺沒有博客（也許是我不造？( ?? ω ?? )y）現(xiàn)在正在碼USACO給的標(biāo)答…

COPYRIGHT@丁爺爺

代碼是我自己的，因?yàn)槭怯弥羔槍懙臅?huì)有點(diǎn)長(zhǎng)，丁爺爺?shù)拇a只有60+。總之祝丁爺爺繼續(xù)超神下去……

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #define lnum 3 7 using namespace std; 8 const int MAXK=1000; 9 const int MAXN=20*15+1; 10 int cnt=-1; 11 struct ACauto 12 { 13 int id; 14 ACauto* next[lnum]; 15 ACauto* fail; 16 ACauto() 17 { 18 id=++cnt; 19 for (int i=0;i<lnum;i++) next[i]=NULL; 20 fail=NULL; 21 } 22 }; 23 ACauto* rt=new ACauto(); 24 int go[MAXN][lnum];//編號(hào)為i的節(jié)點(diǎn)的三個(gè)后繼的編號(hào)，如果不存在則為0 25 int combo[MAXN];//編號(hào)為i的節(jié)點(diǎn)及其后綴能夠產(chǎn)生的最大匹配數(shù) 26 int dp[MAXN][MAXK];//在編號(hào)為i的節(jié)點(diǎn)上再走j步能夠達(dá)到的最大值 27 int n,k; 28 29 void insert(ACauto* rt,char* str) 30 { 31 int len=strlen(str); 32 ACauto* now=rt; 33 for (int i=0;i<len;i++) 34 { 35 int index=str[i]-'A'; 36 if (now->next[index]==NULL) 37 { 38 now->next[index]=new ACauto(); 39 } 40 go[now->id][index]=now->next[index]->id; 41 now=now->next[index]; 42 } 43 combo[now->id]=1; 44 //在不包含后綴的情況下，當(dāng)前結(jié)尾可以產(chǎn)生一個(gè)匹配 45 } 46 47 void buildfail(ACauto* rt) 48 { 49 queue<ACauto*> que; 50 que.push(rt); 51 while (!que.empty()) 52 { 53 ACauto* head=que.front();que.pop(); 54 for (int i=0;i<lnum;i++) 55 { 56 if (head->next[i]==NULL) continue; 57 if (head==rt) 58 head->next[i]->fail=rt; 59 else 60 { 61 ACauto* tmp=head->fail; 62 while (tmp!=NULL) 63 { 64 if (tmp->next[i]!=NULL) 65 { 66 head->next[i]->fail=tmp->next[i]; 67 break; 68 } 69 else 70 tmp=tmp->fail; 71 } 72 if (tmp==NULL) head->next[i]->fail=rt; 73 } 74 combo[head->next[i]->id]+=combo[head->next[i]->fail->id]; 75 //當(dāng)前節(jié)點(diǎn)及其字符串后綴的節(jié)點(diǎn)均可能為模式串，故每次都要沿著指針計(jì)算這一步能夠產(chǎn)生的新的匹配數(shù)。由于計(jì)算時(shí)累加的，只需沿fail指針走一步即可。 76 que.push(head->next[i]); 77 } 78 } 79 } 80 81 void init() 82 { 83 memset(go,0,sizeof(go)); 84 memset(combo,0,sizeof(combo)); 85 scanf("%d%d",&n,&k); 86 for (int i=0;i<n;i++) 87 { 88 char str[1000]; 89 scanf("%s",str); 90 insert(rt,str); 91 } 92 buildfail(rt); 93 } 94 95 void dp_process() 96 { 97 memset(dp,0,sizeof(dp)); 98 for (int i=0;i<=cnt;i++) dp[0][i]=combo[i]; 99 int cur=0; 100 for (int l=1;l<=k;l++) 101 { 102 cur^=1; 103 for (int i=0;i<=cnt;i++) 104 { 105 dp[cur][i]=0; 106 for (int j=0;j<lnum;j++) 107 dp[cur][i]=max(dp[cur][i],combo[i]+dp[cur^1][go[i][j]]); 108 } 109 } 110 printf("%d",dp[cur][0]); 111 } 112 113 int main() 114 { 115 init(); 116 dp_process(); 117 return 0; 118 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/iiyiyi/p/5523810.html

總結(jié)

以上是生活随笔為你收集整理的【AC自动机+DP】USACO2012 JAN GOLD_Video Game Combos的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。