洛谷P1026 统计单词个数

一道神仙语文题（其实是出题人语文没学好）

这道题最坑的地方在于对题意的理解，“当选用一个单词之后，其第一个字母不能再用 ”，指的是单词不能共用开头,而不是在整个段中以该字母开头的单词都不能再用

给两份代码，一个用到了STLstring的一些函数，一个是朴素模拟

朴素模拟

#include<bits/stdc++.h>
using namespace std;

#define go(i,a,b) for(int i=a;i<=b;++i)
#define com(i,a,b) for(int i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof(a))

typedef long long ll;

string s,a[10];
int p,m,n;
int f[55][210];

int get(int l,int r){
    int ans=0;
    go(j,l,r){
        go(i,1,p){
            if(a[i][0]==s[j]){
                int k;
                for(k=0;k<a[i].size();++k){
                    if(j+k>r) break;
                    if(a[i][k]!=s[j+k]) break;
                }
                if(k==a[i].size()){
                    ++ans;
                    break; 
                }
            }
        }
    }
    return ans;
}

int main(){
    //freopen("input.txt","r",stdin);
    cin>>p>>m;
    s=" ";
    string tmp;
    go(i,1,p){
        cin>>tmp;
        s+=tmp;
    }
    cin>>p;
    go(i,1,p) cin>>a[i];
    n=s.size()-1;
    go(i,1,n) f[1][i]=get(1,i); 
    go(i,2,m)
        go(j,i,n)
            go(k,i-1,j-1)
                f[i][j]=max(f[i][j],f[i-1][k]+get(k+1,j));
    printf("%d\n",f[m][n]);
    return 0;
}

STL

#include<bits/stdc++.h>
using namespace std;

#define go(i,a,b) for(int i=a;i<=b;++i)
#define com(i,a,b) for(int i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof(a))

typedef long long ll;

string s,a[10];
int p,m,n;
int f[1000][1000],sum[210][210];

bool check(int l,int r){
    string x=s.substr(l,r-l+1);
    go(i,1,p) if(x.find(a[i])==0) return 1;
    return 0;
}

void init(){
    com(i,n,1)
        com(j,i,1){
            sum[j][i]=sum[j+1][i];
            if(check(j,i)) ++sum[j][i];
        }
}

int main(){
    //freopen("input.txt","r",stdin);
    cin>>p>>m;
    s=" ";
    string tmp;
    go(i,1,p){
        cin>>tmp;
        s+=tmp;
    }
    cin>>p;
    go(i,1,p) cin>>a[i];
    n=s.size()-1;
    init();
    go(i,1,n) f[1][i]=sum[1][i];    
    go(i,2,m)
        go(j,i,n)
            go(k,i-1,j-1)
                f[i][j]=max(f[i][j],f[i-1][k]+sum[k+1][j]);
    printf("%d\n",f[m][n]);
    return 0;
}

洛谷P1026 统计单词个数

原文：https://www.cnblogs.com/White-star/p/11495827.html