终于正常一点了-1.11考试-解题报告

· · 个人记录

T1和T3都是比较可爱的。

T2

DP好题，然而被我用暴力踩标算了...

感觉这种“删掉之后两边拼起来”的题都特别恶心。

看到这个题，容易想到区间DP，但是怎么拼起来呢？

我们可以加一维状态。设g[l][r][k]表示把[l,r]的字符串删除一部分，删到Trie树上的k号节点，最少要删多少次。

转移：

如果下一位匹配的话，g[l][r][k]\to g[l][r+1][tre[k][w]]

但是我们可能中间跳过了一段，因为那一段被删除了，于是有：g[l][p][k]+g[p+1][r][0]\to g[l][r][k]（g[l][r][0]表示这一段删完了）

最后求答案的话，再做一遍背包即可。

signed main()
{
#ifdef M207
    freopen("in.in","r",stdin);
    // freopen("out.out","w",stdout);
#endif
    in(n,m,K);
    scanf("%s",s+1);
    for(ri i=1; i<=m; ++i)
    {
        static char tc[25];
        scanf("%s",tc+1);
        ins(tc,strlen(tc+1));
    }
    mem(g,0x3f);
    for(ri i=0; i<=n; ++i) g[i+1][i][0]=0;
    for(ri len=1; len<=n; ++len)
        for(ri l=1,r=len; r<=n; ++l,++r)
        {
            for(ri p=l; p<=r; ++p)
                if(g[p+1][r][0]<K)
                {
                    int w=s[p]-'a';
                    for(ri i=0; i<=tot; ++i)
                        if(tre[i][w]) upd(g[l][r][tre[i][w]],g[l][p-1][i]+g[p+1][r][0]);
                }
            for(ri k=1; k<=tot; ++k)
                if(ed[k]) upd(g[l][r][0],g[l][r][k]+1);
        }
    mem(f,0x3f);
    f[0][0]=0;
    for(ri i=1; i<=n; ++i)
        for(ri j=0; j<=K; ++j)
        {
            upd(f[i][j],f[i-1][j]+1);
            if(j) upd(f[i][j],f[i][j-1]);
            for(ri k=1; k<=i; ++k)
                if(j>=g[k][i][0]) upd(f[i][j],f[k-1][j-g[k][i][0]]);
        }
    out(f[n][K]);
    return 0;
}