题解：P7458 [CERC2018] Clockwork ||ange

yz_zy · 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] 可以从多个状态转移过来，那么这些状态之间应该如何做取舍呢？

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

证明：

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

那么可分为 3 种情况：

证毕。

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

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;
}