题解 P9229【扩展九连环】

Graphcity · 2023-04-22 22:17:23 · 题解

看到这种跟汉诺塔非常像的解谜游戏，首先就是需要拆解它们的步骤。大体的步骤分三步：

1. 把前面 n 个字符变成规则串。
2. 消耗一步装上第 n+1 个环。
3. 把前面 n 个字符变成 11111... 的形式。

我们设 f(x,y,z) 表示考虑前 x 个字符，当前状态是后缀 y（y=0 表示全零，y=n+1 表示全一），最终需要变成后缀 z 的所需步数。那么答案就等于 f(n,0,n)+1+f(n,n,n+1)。

• 对于 f(n,0,n)

我们从后往前扫描，如果当前的字符和最终这个位置需要的字符一致则跳过。此时我们找到了第一个不符的位置 i，我们需要对它进行一次变换。进行变换就必须得让前 i-1 个字符变成规则串长为 i-1 的后缀，变换完后再改成目标状态。

写成式子就是 f(n,0,n)=f(i-1,0,i-1)+1+f(i-1,i-1,n)。

• 对于 f(n,n,n+1)

我们还是从后往前扫描到第一个不符合的位置，然后再对它进行变换。类似的，可以得到 f(n,n,n+1)=f(i-1,n,i-1)+1+f(i-1,i-1,n+1)。

我们注意到这个三维的状态中每一步都有一组数字是相同的。自然地，设 f(x,y)=f(x,y,x)，g(x,y)=f(x,x,y)，那么可以得到：

使用记搜实现，状态有 O(n^2) 种，每次扫描时间 O(n)，总时间复杂度 O(n^3)，跑的很快。

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=2e3,Mod=1e9+7;

int n,ans,s[Maxn+5];
int f[Maxn+5][Maxn+5],g[Maxn+5][Maxn+5];
bool fv[Maxn+5][Maxn+5],gv[Maxn+5][Maxn+5];
int F(int x,int y);
int G(int x,int y);

inline int Get(int x,int y)
{
    if(x==0) return 0; if(x==n+1) return 1;
    return s[n-(x-y)];
}
inline int F(int x,int y)
{
    if(x==0) return 0;
    if(fv[x][y]) return f[x][y];
    int res=0;
    for(int i=x;i;i--) if(Get(x,i)!=Get(y,i))
        {res=(F(i-1,y)+1+G(i-1,x))%Mod; break;}
    fv[x][y]=1,f[x][y]=res; return res;
}
inline int G(int x,int y)
{
    if(x==0) return 0;
    if(gv[x][y]) return g[x][y];
    int res=0;
    for(int i=x;i;i--) if(Get(x,i)!=Get(y,i))
        {res=(F(i-1,x)+1+G(i-1,y))%Mod; break;}
    gv[x][y]=1,g[x][y]=res; return res;
}

int main()
{
    scanf("%d",&n);
    For(i,1,n) scanf("%1d",&s[i]);
    ans=(F(n,0)+1+G(n,n+1))%Mod;
    cout<<ans<<endl;
    return 0;
}

注意到一个时间复杂度瓶颈在于扫描上。事实上，扫描需要解决的问题就是一个串不同前缀的最长公共后缀。我们再设一个动态规划数组 h(x,y) 表示前缀 x,y 的最长公共后缀。有转移

注意第二，三种转移应放到第一种转移后进行，否则会出现冲突。总时间复杂度 O(n^2)，但时间效率反而不如上面的代码。

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=2e3,Mod=1e9+7;

int n,ans,s[Maxn+5],h[Maxn+5][Maxn+5];
int f[Maxn+5][Maxn+5],g[Maxn+5][Maxn+5];
bool fv[Maxn+5][Maxn+5],gv[Maxn+5][Maxn+5];
int F(int x,int y);
int G(int x,int y);

inline int F(int x,int y)
{
    if(x==0) return 0;
    if(fv[x][y]) return f[x][y];
    int res=0,id=(y>=1 && y<=n?n-(y-x):y);
    int len=min(x,h[n][id]),i=x-len;
    if(i) res=(F(i-1,y)+1+G(i-1,x))%Mod;
    fv[x][y]=1,f[x][y]=res; return res;
}
inline int G(int x,int y)
{
    if(x==0) return 0;
    if(gv[x][y]) return g[x][y];
    int res=0,id=(y>=1 && y<=n?n-(y-x):y);
    int len=min(x,h[n][id]),i=x-len;
    if(i) res=(F(i-1,x)+1+G(i-1,y))%Mod;
    gv[x][y]=1,g[x][y]=res; return res;
}

int main()
{
    scanf("%d",&n);
    For(i,1,n) scanf("%1d",&s[i]);
    For(i,1,n) For(j,1,n) if(s[i]==s[j])
        h[i][j]=h[i-1][j-1]+1;
    For(i,1,n) if(s[i]==0) h[0][i]=h[i][0]=h[0][i-1]+1;
    For(i,1,n) if(s[i]==1) h[n+1][i]=h[i][n+1]=h[n+1][i-1]+1;
    ans=(F(n,0)+1+G(n,n+1))%Mod;
    cout<<ans<<endl;
    return 0;
}