题解 P2506 【[SCOI2008]劣质编码】

· · 题解

又来一道玄学题orz

我们发现这题的状态数应该不会太多，我们只要能找到合适的压缩状态的办法，就能过题。

因为这个cnt只到3的范围左右，于是我们考虑dp，如果我们能压出的是dp的数组？并且这个里面的dp值不会很大，3左右的最多。

于是我们开始考虑怎么dp，记录当前匹配到第i个串的第j位的个数有多少？我们只需要维护这个dp值就可以。

这个非常好转移，如果填完了，就把所有新开始的位置加上填完的总数组解，反之我们就是向前一位转移。

于是我们考虑如果有某一个字符串填完，把这个填完的总数相加，如果大于3就直接找到答案了，反之我们就继续bfs。

这里具体的实现我们用一个vector来压一个dp数组，这个dp数组我们把i个串的都拼在一起，搞一个一位数组存在vector里面就好。

然后我们用一个map来映射一下这个vector，转移就是枚举‘0’~‘1’然后不断bfs，大致是这样的一个思路。

具体复杂度我也不会证，但是跑的飞快，就O(能过)

代码：

#include<bits/stdc++.h>
#define LL long long
#define vi vector<int>
using namespace std;
int n,id[35][55],totl,dfn;
string str[35];
vi s,t;map<vi,int>mp;
queue<vi>q;
int main(){
    scanf("%d",&n);
    for(int i=1,l;i<=n;i++){
        cin>>str[i];l=str[i].size();totl+=l;
        if(!l){puts("0");return 0;}
        for(int j=0;j<l;j++)id[i][j]=dfn++;
    }
    s.resize(totl);t.resize(totl);
    for(int i=1;i<=n;i++)s[id[i][0]]=1;
    mp[s]=0;q.push(s);
    while(!q.empty()){
        vi u=q.front();q.pop();int ns=mp[u];
        for(char ch='0';ch<='1';ch++){
            for(int i=0;i<totl;i++)t[i]=0;
            int ed=0;
            for(int i=1,l;i<=n;i++){
                l=str[i].size();
                for(int j=0;j<l;j++)if(str[i][j]==ch){
                    if(j==l-1)ed+=u[id[i][j]];else t[id[i][j+1]]=u[id[i][j]];
                }
            }
            if(ed>=3){printf("%d\n",ns+1);return 0;}
            for(int i=1;i<=n;i++)t[id[i][0]]=ed;
            if(!mp.count(t))mp[t]=ns+1,q.push(t);
        }
    }
    puts("-1");
    return 0;
}