P5757 [NOI2000] 古城之谜 题解

· · 题解

题目描述

给定 n 和 n 个信息，每个信息包含一个词性 a （只有三种：名，动，辅）和对应的词 mot ，形为“ a.mot ”。（一次可能多词性）

最后给一个长度不大于 5KB 的冰峰文文章，将这篇冰峰文文章划分为最少的句子，在这个前提下，将文章划分为最少的单词时，求划分的句子数量和单词数量。

划分标准： （别问我为什么盗图。。

1\leq n\leq 10^3\ \ \ \ mot.len\leq 20

solution

首先要搞懂题目中的图是什么玩意（我真的看了好久都没看懂。。）

所有语法简述下来就是：

1.名词短语是许多个辅词加一个名词组成的。

2.动词短语是许多个辅词加一个动词组成的。

3.一个句子以名词短语开头，名词短语和动词短语交替出现而组成的。

4.文章为多句话组成。

所以对于任意词，有四种类型：

1.名词。

2.动词。

3.辅名词的辅词。

4.辅动词的辅词。

状态应该很自然了。。（要什么设什么呗）

$f[j][i][1]$ 指前 $i$ 个字母，最后一个单词是动词，构成了 $j$ 个句子的最小单词数。 $f[j][i][2]$ 指前 $i$ 个字母，最后一个单词是辅词，后面要接动词，构成了 $j$ 个句子的最小单词数。 $f[j][i][3]$ 指前 $i$ 个字母，最后一个单词是辅词，后面要接名词，构成了 $j$ 个句子的最小单词数。 状态转移方程就按照语法看能否转移就行 $f[j][i][0] \Longrightarrow \min{(f[j][k][1/3],f[j-1][k][0/2])} f[j][i][1] \Longrightarrow \min{(f[j][k][0/2])} f[j][i][2] \Longrightarrow \min{(f[j][k][0/2])} f[j][i][3] \Longrightarrow \min{(f[j][k][1/3],f[j-1][k][0/1])}

实际上看式子的话， j 那一维可以滚动起来。（虽然不滚掉好像问题不大，但省空间多好。。）

最后答案就是按题目来，求一个最小的 ans ，存在 f[ans][len][0/1] ，如果都存在，取较小值。

明显 $DP$ 的复杂度不允许我们每次枚举所有单词再去比较。 所以想到了用一个比较实用的东西 $trie$ 可以把速度拉起来。 基本上这题就搞定了，就是注意一定把数组开稍微大点（我因为忽略数组大小而傻乎乎地去调了半个小时程序了） ### $code 
#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;
}

（话说为什么没题解呀。。