USACO chapter 2 section 2.3 The Longest Prefix

USER: tian tianbing [tbbd4261]
TASK: prefix
LANG: C++
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 6916 KB]
Test 2: TEST OK [0.000 secs, 6916 KB]
Test 3: TEST OK [0.000 secs, 6916 KB]
Test 4: TEST OK [0.000 secs, 6916 KB]
Test 5: TEST OK [0.022 secs, 6916 KB]
Test 6: TEST OK [0.173 secs, 6916 KB]
All tests OK.

Your program ('prefix') produced all correct answers! This is your submission #5 for this problem. Congratulations!



DP:dp[i]=(dp[i]||dp[i-ll]);
   dp[i]表示前缀可到达的长度为i。如果对于所有dp[i-ll]均为假则dp[i]不可能为真。
/*
ID:tbbd4261
PROG:prefix
LANG:C++
*/

#include
<iostream>
#include
<fstream>
#include
<string>
#include
<cstring>
using namespace std;
ifstream fin(
"prefix.in");
ofstream fout(
"prefix.out");
const int MAX=2000005;
string prefix[205];
char s[MAX]={0};
bool dp[MAX]={0};
int cnt=0,n=0,i=0,j=0,k;

int main()

    
while(fin>>prefix[++cnt], prefix[cnt]!=".")
                ;
    cnt
--;
    
char ch; i=0;
    
while(fin>>ch)s[++i]=ch;
    n
=i;  
    
bool flag;
    dp[
0]=true;
    
for( i=1; i<=n; i++)
    {
         
for(j=1; j<=cnt; j++)
         {
                  flag
=true;
                  
int ll=prefix[j].length();
                  
if(i<ll)continue;
                  
for(k=0; k<ll; k++)
                     
if(prefix[j][k]!=s[i-ll+1+k])
                     {
                             flag
=falsebreak;
                     }
                     
if(flag)dp[i]=(dp[i]||dp[i-ll]);
                     if(dp[i])break;
         }  
    }
    
    
for(k=n; k>=0; k--)
             
if(dp[k]) { fout<<k<<endl; break;}
    
return 0;
}

posted on 2010-08-02 11:22 田兵 阅读(164) 评论(0)  编辑 收藏 引用 所属分类: USACO


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年5月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜