#include<bits/stdc++.h>
#define reg register
using namespace std;
typedef long long ll;
const int N=1e3+10,M=6e3+10,K=3e4+10;
const int INF=0x3f3f3f3f;
int n,m,mlth,f[2][M][4],tri[M][24],tot,op,ans1,ans2;
char sw[M],sd[M];
struct trie{
    int tr[26],opt,it;
    inline void clear(){
        memset(tr,0,sizeof(tr));
        it=-1;opt=0;
    }
}trie[K];
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline void insert(char s[],int lth,int opt){
    int id=0,val;
    for(int i=2;i<lth;++i){
        val=s[i]-'a';
        if(!trie[id].tr[val]){
            trie[++tot].clear();
            trie[tot].it=val;
            trie[id].tr[val]=tot;
        }
        id=trie[id].tr[val];
    }
    trie[id].opt|=opt;
}
inline int find(int lt,int rt){
    int id=0,val;
    for(int i=lt;i<=rt;++i){
        val=sd[i]-'a';
        if(!trie[id].tr[val])return 0;
        id=trie[id].tr[val];
    }
    return trie[id].opt;
}
inline void mian(){
    ans1=0;ans2=INF;
    trie[0].clear();
    memset(tri,-1,sizeof(tri));
    memset(f,INF,sizeof(f));
    for(int i=1;i<=n;++i){
        scanf("%s",sw);m=strlen(sw);
        mlth=max(m,mlth);
        if(sw[0]=='n')insert(sw,m,1);
        else if(sw[0]=='v')insert(sw,m,2);
        else if(sw[0]=='a')insert(sw,m,4);
    }
    scanf("%s",sd+1);m=strlen(sd+1)-1;
    f[0][0][0]=0;
    for(int lin=1;lin<=m;++lin){
        int now=op^1,pre=op;
        for(int i=1;i<=m;++i){
            memset(f[now][i],INF,sizeof(f[now][i]));
            int lim=max(i-mlth,0);
            for(int j=i-1;j>=lim;--j){
                if(tri[j+1][i-j]==-1)
                    tri[j+1][i-j]=find(j+1,i);
                int opti=tri[j+1][i-j],nowi,prei;
                if(opti&1){
                    nowi=min(f[now][j][1],f[now][j][3]);
                    prei=min(f[pre][j][0],f[pre][j][2]);
                    f[now][i][0]=min(f[now][i][0],nowi+1);
                    f[now][i][0]=min(f[now][i][0],prei+1);
                }//不能有else
                if(opti&2){
                    nowi=min(f[now][j][0],f[now][j][2]);
                    f[now][i][1]=min(f[now][i][1],nowi+1);
                }//不能有else
                if(opti&4){
                    nowi=min(f[now][j][0],f[now][j][2]);
                    f[now][i][2]=min(f[now][i][2],nowi+1);
 
                    nowi=min(f[now][j][1],f[now][j][3]);
                    prei=min(f[pre][j][0],f[pre][j][1]);
                    f[now][i][3]=min(f[now][i][3],nowi+1);
                    f[now][i][3]=min(f[now][i][3],prei+1);
                }//不能有else
            }
        }
        ans2=min(f[now][m][0],f[now][m][1]);
        if(ans2!=INF){ans1=lin;break;}
        op^=1;
    }
    printf("%d\n%d\n",ans1,ans2);
}
int main(){
    n=read();
    mian();
    return 0;
}

我还没提交

当心辅词不能作结尾

其他没什么了。朴素判匹配也能0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

用Trie辅助转移，进行DP……

...............

检索树存单词...

DP出解...

记录前I个字符,最后一个单词为名词或动词时最少的句子数和单词数,状态转移就是前I个字符,最后J个为一个单词,取所有合法情况中的最小值......

理解那个破范式

一个名词短语是一个名词前加若干个（可以为0）辅词。

一个动词短语是一个动词前加若干个（可以为0）辅词。

而一个句子是以名词短语开头，名动短语交换，最后可以以名词或动词短语结尾。

搜索文章中i开头的所有名动短语，用链表分开存储。

设dp表示文章中i开头文章在匹配j短语(1－名词,2－动词)后的最优解（解的状态是二维的）。

如果j=1，此时i处匹配名词短语k后，可以令起一个句子（接一个名词短语），也可以在本句接一个动词短语。

如果j=2，此时i处匹配动词短语k后，只能在本句接一个名词短语。

用类动态规划的方法可以求出dp的值，需要输出的结果就是dp[1,1]。

因为很多的dp值根本不需要计算，所以用记忆化搜索来做。

时间复杂度最坏情况下是O(mn)，m是文章长度。实际效果瞬间出解。

Flag 　　Accepted

题号 　　P1299

类型(?) 　　动态规划

通过 　　50人

提交 　　151次

通过率 　　33%

难度 　　3

哈哈哈,第50人

交了N次每次错的还不一样，有超时有WA，无语了。。。。最多只过了6个...trie还没朴素高不知道怎么回事....

看懂题，仔细想，别想复杂了

开了个大Hash判重，复杂度是O(文章长度*单词长度)

1.41K的代码……AC

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

字母检索树 秒杀