自动搬运

查看原文

来自洛谷，原作者为

	Graphcity 循此苦旅，终抵繁星。

搬运于2025-08-24 22:46:34，当前版本为作者最后更新于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)$，那么可以得到：

$$\begin{cases} f(x,y)&=f(i-1,y)+1+g(i-1,x)\\ g(x,y)&=f(i-1,x)+1+g(i-1,y) \end{cases} $$

使用记搜实现，状态有 $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$ 的最长公共后缀。有转移

$$\begin{cases} h(x,y)&=h(x-1,y-1)+1 & s_x=s_y,x>0,y>0\\ h(x,0)=h(0,x)&=h(0,x-1)+1 & s_x=0,x>0\\ h(x,n+1)=h(n+1,x)&=h(n+1,x-1)+1 & s_x=1,x>0 \end{cases} $$

注意第二，三种转移应放到第一种转移后进行，否则会出现冲突。总时间复杂度 $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;
}