动态规划详解

P1470 [USACO2.3]最长前缀 Longest Prefix

这道题目感觉和  P1832 A+B Problem（再升级）有点类似。

将一个合法答案再加上另外一个合法答案组成新的组合，而这个组合一定合法。

因此我们枚举每一个可行解，将字符串 S 的一部分减去一个可行解，如果剩下部分也是可行解，则该部分可行。

所以我们定义 dp[i] 数组是以 i 结尾的 S 的一部分，标记该区域是否可行。

其中要注意：S 的一部分的长度一定大于等于一个可行解的长度，否则会有负数下标越界。

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N=1e4+10,NN=1e4+10;
 5 ll n=0,m,k,x,y,u,v,w,cnt=0,ans=0,t=0,l,r,len,T;
 6 ll mini=INT_MAX,maxi=0;
 7 string s,s1[N],s2,S=" ";
 8 ll dp[N]={1},a[N];
 9 ll f(int id){
10     for(int i=0;i<n;i++){
11         ll len1=s1[i].size();
12         if(id>=len1&&dp[id-len1]&&s1[i]==S.substr(id-len1+1,len1)){
13             ans=id;
14             return 1;
15         }
16     }
17     return 0;
18 }
19 int main(){
20       for(string s;cin>>s,s!=".";s1[n++]=s);
21       for(string s;cin>>s;S+=s);
22     for(int i=1;i<=S.size();i++){
23         dp[i]=f(i);
24     }
25     cout<<ans;
26     return 0;
27 }