USACO-Section2.3 Longest Prefix

2017-9-6

题目描述

表示字符串 S 符合条件的前缀的最大长度

解答

动态规划

代码

/* ID: 18795871 PROG: prefix LANG: C++ */ #include<iostream> #include<fstream> #include<cstring> using namespace std; const int N = 200000,M = 200;ifstream fin("prefix.in"); ofstream fout("prefix.out");int dp[N+1],t=1,m=0;; char x[M+2][12],y[80],S[N+2],rr[12];void res(int i,int l){memset(rr,'\0',sizeof(rr)); int j,k=0;for (j=i;j<i+l;j++){rr[k++]=S[j];}rr[k]='\0'; }bool fun(int l){for (int i=l-m+1;i<=l;i++){if (dp[i]) return false;} return true; } int main(){int i,j,l;fin>>x[t];while (x[t][0]!='.'){t++;fin>>x[t];}fin>>y;strcat(S,y);l=strlen(y);while (1){if(!(fin>>y)){break; }strcat(S,y);}bool f=false;for (i=1;i<t;i++){l=strlen(x[i]);res(0,l);if (strcmp(rr,x[i])==0){f=true;break;}}if (!f){fout<<"0"<<endl;return 0;}for (int i=0;i<t;i++){l=strlen(x[i]);m=max(m,l); //求出最长字符串长度 }for (j=1;j<=strlen(S);j++){for (i=1;i<t;i++){l=strlen(x[i]);if (j>=l){res(j-l,l);if (strcmp(rr,x[i])==0){dp[j]=max(dp[j-l]+l,dp[j]);}}}if (j>=m){if (fun(j)) break;}}int res=dp[0];for (i=1;i<=strlen(S);i++){res=max(res,dp[i]);}fout<<res<<endl;return 0; } 新人创作打卡挑战赛发博客就能抽奖！定制产品红包拿不停！

总结

以上是生活随笔为你收集整理的USACO-Section2.3 Longest Prefix的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。