Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
贴个代码,c++ 700ms+,g++ tle#include <iostream> #include <cstring> #define M 110 using namespace std; char str[M][M],text[1000001]; int n,a[M]; __int64 dp[1000001]; int main() { // freopen("1.txt","r",stdin); while(scanf("%d",&n)!=EOF) { int i,j,k,p,q,h,l; for(i=1;i<=n;i++) { scanf("%s",str[i]+1); a[i]=strlen(str[i]+1); } scanf("%s",text+1); dp[0]=0; q=strlen(text+1); for(i=1;i<=q;i++) { dp[i]=dp[i-1]; for(j=1;j<=n;j++) { if(str[j][a[j]]==text[i]) { for(k=i-1,p=a[j]-1,h=1;h<=1000&&p>0&&k>0;k--,h++) { if(str[j][p]==text[k]) p--; } if(p==0) { if(dp[k]+a[j]>dp[i]) dp[i]=dp[k]+a[j]; } } } } printf("%I64d\n",dp[q]); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator