自动搬运

查看原文

来自洛谷，原作者为

	yz_zy **

搬运于2025-08-24 22:30:05，当前版本为作者最后更新于2025-04-26 15:56:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P7458 [CERC2018] Clockwork ||ange

此题可考虑 $dp$.

设 $dp[i][j]$ 表示的状态是第 $i$ 次跳跃跳了 $j$ 步后的最佳畜栏轮廓。

例如：

初状态为 $10010$，

则 $dp[1][1]=11011=27$，$dp[1][2]=10110=22$，$dp[2][1]=11111=31$。

显然就有 $dp[i-1][k] \to dp[i][j]$，其中

$$dp[i][j]=(dp[i-1][k]>>j)\; \| \; dp[i-1][k]$$

但是有一个问题，$dp[i][j]$ 可以从多个状态转移过来，那么这些状态之间应该如何做取舍呢？

我们可以猜测出来，这应该是取最值，即：

$$dp[i][j]=max((dp[i-1][k]>>j)\; \| \; dp[i-1][k]\; ,\;dp[i][j]) $$

证明：

设有两串二进制数 $a,b$ 且 $a>b$。

那么可分为 $3$ 种情况：

1. $a$ 中 $1$ 的数量要多于 $b$ 中的 $1$ 的数量，显然要选择 $a$。

2. $a$ 中 $1$ 的数量与 $b$ 中 $1$ 的数量相等，因为 $a>b$ ，所以 $a$ 中的 $1$ 都在高位上，这些 $1$ 都可以往低位走，它的潜力更大，故选择 $a$。

3. $a$ 中 $1$ 的数量小于 $b$ 中 $1$ 的数量，$b$ 中的 $1$ 全部堆积在低位上，高位的很难顾及到，故选择 $a$。

证毕。

这么做下来竟然可以拿到最优解！

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
string s;
int f[N][45],n;
signed main(){
	cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(false);
	cin>>s;n=s.size();s=' '+s;
	int now=0;
	for(int i=n;i>=1;i--){
		now=now+(int)(s[i]-'0')*((int)1<<(n-i));
	}
	for(int i=1;i<=40;i++) f[0][i]=now;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=40;j++){
			for(int k=1;k<=40;k++){
				f[i][j]=max((f[i-1][k]>>j)|f[i-1][k],f[i][j]);
			}
		}
	}
	for(int i=0;i<=n;i++){
		for(int j=1;j<=40;j++){
			if((int)f[i][j]==(int)(((int)1<<n)-1)){
				cout<<i;
				return 0;
			}
		}
	}
	cout<<-1;
	return 0;
}