题解：P2581

· · 题解

本题题目、样例有误。

正确的题面：

洛谷P6701

LOJ (数据水一点)

使用区间DP+状压：

转化为将给定的字符串能压缩成的只含有 S 的最短字符串。

对于给定的分裂（合并）规则，也就是两个字符合并为一个字符，我们用状压思想，以二进制来存储这两种字符可以合并为那些种类的字符，也就是:

c[get(ins[1])][get(ins[2])]|=(1<<(get(ins[0])));

再考虑如何DP。

设 dp_{i,j} 表示区间 [i,j] 中的答案，git_{i,j} 表示区间 [i,j] 可以合并成为那些字符。

在进行区间DP的同时，更新 git_{i,j}，如果合并出了 S，则 dp_{i,j}=1。

我们还可以进行一些优化：

  1. 开小数组。
  2. 很多大佬采用的是枚举每个字符，其实可以直接存每一种合并，再来枚举，这样会快一些。

具体看代码吧，还是比较好理解的。

#include<bits/stdc++.h>

using namespace std;

const int MX=105;
#define LL long long
#define inf 0x3f3f3f3f

#define modn 10000

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int m;//规则数

char ins[10];
int c[30][30];//合并用

int git[MX][MX];

char s[MX];
int n;

inline int get(char x)
{
    return x-'A'+1;//1~26
}

int dp[MX][MX];

inline void csh()
{
    memset(dp,0x3f,sizeof(dp));
    memset(git,0,sizeof(git));
}

struct tCod
{
    int x,y;
}cod[800];
int idx=0;

int main(int argc, char const *argv[])
{
    m=read();
    for(int i=1;i<=m;i++)
    {
        scanf("%s",ins);
        if(c[get(ins[1])][get(ins[2])]==0)
        {
            cod[++idx]=tCod{get(ins[1]),get(ins[2])};
        }
        c[get(ins[1])][get(ins[2])]|=(1<<(get(ins[0])));

    }
    int T;
    T=read();
    while(T--)
    {
        csh();
        scanf("%s",s+1);
        n=strlen(s+1);
        for(int i=1;i<=n;i++)
        {
            if(s[i]=='S')
            {
                dp[i][i]=1;
            }
            git[i][i]|=(1<<(get(s[i])));
        }
        for(int len=0;len<n;len++)
        {
            for(int l=1;l+len<=n;l++)
            {
                int r=l+len;
                //l~k k+1~r
                for(int k=l;k<=r-1;k++)
                {
                    dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
                    for(int q=1;q<=idx;q++)
                    {
                        int x=cod[q].x,y=cod[q].y;
                        if(c[x][y])//如果这两个字符能合并
                        {
                            //git是放单字符的多情况的，如果能合并的话就合并，一个区间合并成一个字符，然后记录这一个字符有多少种情况
                            if((git[l][k]&(1<<(x)))&&((git[k+1][r])&(1<<(y))))
                            {
                                git[l][r]|=c[x][y];
                                //printf("%d %d %d %d\n",l,k,r,c[x][y]);
                            }
                        }
                    }   
                    if((git[l][r]&(1<<(get('S')))))
                    {
                        dp[l][r]=1;//如果合并出S了，就直接变成1
                    }
                }
            }
        }
        if(dp[1][n]==inf) printf("NIE\n");
        else printf("%d\n",dp[1][n]);
    }
    return 0;
}