題目鏈接：點擊查看

題目大意：給出 n 個模式串每個模式串都有一個價值，要求構(gòu)造出一個長度為 m 的字符串，每個模式串出現(xiàn)一次都會得到一次相應(yīng)的價值，問如何構(gòu)造可以使得最終的價值總和最大

題目分析：做過一道加強版的題目：https://blog.csdn.net/qq_45458915/article/details/104235188

多余的功能刪掉就好，有個不太一樣的細節(jié)就是，上面的那個題目的字符串不允許共用，但這個題目的字符串允許共用，所以需要在 getfail() 函數(shù)中稍作修改，也就是說需要累加一下共用的字符串的貢獻，剩下的直接 dp 就好了，dp[ i ][ j ] 代表構(gòu)造長度為 i 的字符串，當(dāng)前狀態(tài)為 j 時的最大貢獻，傳遞的話在AC自動機的trie樹上跑就好了

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e3+100;int n,m;char s[N];int fail[N],trie[N][26],cnt,sum[N];vector<int>vis[N];int dp[1010][N];//dp[i][j]:長度為 i ，狀態(tài)為 j 時的最大值 void insert_word(int val) {int len=strlen(s);int pos=0;for(int i=0;i<len;i++){int to=s[i]-'a';if(!trie[pos][to])trie[pos][to]=++cnt;pos=trie[pos][to];}sum[pos]+=val; }void getfail() {queue<int>q;for(int i=0;i<26;i++){if(trie[0][i]){fail[trie[0][i]]=0;q.push(trie[0][i]);}}while(!q.empty()){int cur=q.front();q.pop();sum[cur]+=sum[fail[cur]];for(int i=0;i<26;i++){if(trie[cur][i]){fail[trie[cur][i]]=trie[fail[cur]][i];q.push(trie[cur][i]);}elsetrie[cur][i]=trie[fail[cur]][i];}} }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){int val;scanf("%s%d",s,&val);insert_word(val);}getfail();memset(dp,-inf,sizeof(dp));dp[0][0]=0;for(int i=0;i<m;i++)for(int j=0;j<=cnt;j++)for(int k=0;k<26;k++){int nj=trie[j][k];dp[i+1][nj]=max(dp[i+1][nj],dp[i][j]+sum[nj]);}int ans=-inf;for(int i=0;i<=cnt;i++)ans=max(ans,dp[m][i]);printf("%d\n",ans);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的牛客 - 牛妹的考验(AC自动机+dp)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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