P1026

#include<bits/stdc++.h>
using namespace std;
int p,k,num;//p行字符串，分成k个段，num个单词
string d[10],s;//分别是字典和输入的字符串
int cnt[205][205],dp[205][15];
//cnt[i][j]表示[i,j]里单词个数
//dp[i][j]表示0~i分成j个段的最大单词数
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>p>>k;
    for(int i=1;i<=p;i++){
        string t;
        cin>>t;
        s+=t;
    }
    cin>>num;
    for(int i=1;i<=num;i++) cin>>d[i];
    for(int i=0;i<s.size();i++){
        for(int j=i;j<s.size();j++){
        	for(int ttt=i;ttt<=j;ttt++){
        		for(int chk=1;chk<=num;chk++){
        			if(ttt+d[chk].size()-1>j) continue;
        			else if(s.substr(ttt,d[chk].size())==d[chk]){
        				cnt[i][j]++;
        				break;
					}
				}
			}
        }
    }//预处理cnt
//    for(int i=0;i<s.size();i++){
//    	for(int j=i;j<s.size();j++) cout<<i<<' '<<j<<' '<<cnt[i][j]<<endl; 
//	}
    for(int i=0;i<s.size();i++){
    	dp[i][0]=cnt[0][i];
    	for(int j=1;j<=num;j++){
    		for(int ttt=0;ttt<i;ttt++){
    			dp[i][j]=max(dp[i][j],dp[ttt][j-1]+cnt[ttt+1][i]);//dp
			}
		}
	}  
    cout<<dp[s.size()-1][num]<<"\n";   	
    return 0;
}

80pts,WA #2 #3

样例2数据：

1 4
aaaaaaaaaaaaaaaaaaaa
1
aaaa

ans:14
my_output:16