题解 P1026 【统计单词个数】

2019-10-05 19:25:08


一年前看着道题不会做。。。。

(其实这道题一点也不难。。。)

复仇成功。。。。。。。。

暴力跑出对于没一段去间造成的贡献。。

复杂度(n^3slenth[i])的

但实际上远远跑不满

在用dp解决

定义状态dp[i][j]表示到i个字符

分割成j段的最大ans

转移方程 dp[i][j]=dp[k][j-1]+sum[k+1][i]

未免太过显然。。。

放代码

#include<bits/stdc++.h>

using namespace std;

int n,m,s,len,sum[205][205],lenth[11],f[205][55];
string a,b;
string ss[11];

inline void read(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>b;
        a=a+b;
    }
    cin>>s;
    len=a.length();
    for(int i=1;i<=s;i++) cin>>ss[i];
    for(int i=1;i<=s;i++) lenth[i]=ss[i].length();
}

inline void pre_work(){
    for(int i=0;i<len;i++) 
        for(int j=i;j<len;j++)
            for(int k=i;k<=j;k++){
                int flag=1;
                for(int l=1;l<=s;l++){
                    if(k+lenth[l]-1>j) continue;
                    for(int w=0;w<lenth[l];w++){
//                      if(i==0&&j==3&&k==3&&l==1){
//                          cout<<a[k+w]<<" "<<ss[l][w]<<endl;
//                      }
                        if(w==lenth[l]-1&&a[k+w]==ss[l][w]){
                            flag=0;
                            break;
                        }
                        if(a[k+w]!=ss[l][w]) break;
                    }
                    if(flag==0) break;
                }
                if(flag==0) sum[i][j]++;
            }
//  cout<<sum[0][3]<<endl;
//  for(int i=0;i<len;i++) {
//      for(int j=0;j<len;j++)
//          cout<<sum[i][j]<<" ";
//      cout<<endl;
//  }
}

inline void solve(){
    for(int i=0;i<len;i++){
        f[i][1]=sum[0][i];
        for(int j=0;j<i;j++)
            for(int k=2;k<=min(m,j+1);k++){
                f[i][k]=max(f[i][k],f[j][k-1]+sum[j+1][i]);
            }
        }
    cout<<f[len-1][m]<<endl;
}

int main(){
    read();
    pre_work();
    solve();
    return 0;
}