一道重要题

QLWybz / 2024-02-06 / 原文

做题时要根据部分分不断往前推进，而不是上来就干100分，有一些错误的想法不要立刻

否定，一些错误的想法根据修正也能给我们提供重要的信息。

3278 -- Catch That Cow (poj.org)

(前提)别用搜索...

(提示)这道题的贪心是错误的。

贪心思路:

转换成二进制然后将A变成B的前缀，然后不断在二进制后面加零,加一(即$×2,+1$)。

但这个贪心是错误的，我比如说

\[A=(111)_2 \\B=(1111111)_2 \]

用我们的想法操作次数是$8$，但这个样例有一个更优的做法。先给A加上1变成$A=(1000)_2$，然后我们在加零，加到比原来多一个，再减一就好了。

\[A=(1000)_2//加1\\ A=(10000000)_2//×2操作\\ A=(1111111)_2//减1操作 \]

我们可以知道下面要比上面的优，所以我们之前的想法假了，然而我们不能直接放弃我们的第一种想法，因为在很多时候我们的第一种想法是最优的，所以这告诉我们前缀和前缀+1一样重要。这样我们就可以设计转移方程了。

先列出状态:$f[i][0]$表示把A变成长度为$i$的前缀，$f[i][1]$表示把A变成长度为$i$的前缀$+1$。

这道题告诉我们，我们要多方面考虑，然后遇到假的想法，也要把他订正，看看能不能成为有效信息。

我们设计一下转移方程

if(第i位为0){
	f[i][0]=min(f[i-1][0]+1,f[i-1][1]+2);
	f[i][1]=min(f[i-1][0]+2f[i-1][1]+2);
}
else{
	f[i][0]=min(f[i-1][0]+2,f[i-1][1]+2);
	f[i][1]=min(f[i-1][0]+2,f[i-1][1]+1);
}

很多人可能有疑惑，在最后一个方程中的$f[i-1][1]$为什么只加1，我也是问了才会的...

f[i-1][0]:10001     f[i-1][1]:100010
f[i][0]:100011      f[i][1]:100100

其实就是$f[i-1][1]×2$ $...$

答案是$min(f[n][0],f[n][1]+1)$。

code:

#include <iostream>
#include <cstdio>
#include <bitset>
#include <cmath>
using namespace std;
//#define int long long
const int maxn=1e6+5;//注意题目要求
inline int read(){
    int x=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*w;
}
int n,m;
bitset<30> nn;
int dp[1000000][2];
void DP(){
    nn=n;
    int mxn=29;while(nn[mxn]==0) --mxn;
    memset(dp,0x3f,sizeof(dp));
    int tmp=0;
    for(int i=0;i<=mxn;i++){
        tmp=tmp*2+nn[mxn-i];
        dp[i][0]=abs(m-tmp);
        dp[i][1]=abs(m-tmp-1);
    }
    for(int i=1;i<=mxn;i++){
        if(nn[mxn-i]==0){
            dp[i][0]=min(dp[i][0],min(dp[i-1][0]+1,dp[i-1][1]+2));
            dp[i][1]=min(dp[i][1],min(dp[i-1][0]+2,dp[i-1][1]+2));
        }
        else {
            dp[i][0]=min(dp[i][0],min(dp[i-1][0]+2,dp[i-1][1]+2));
            dp[i][1]=min(dp[i][1],min(dp[i-1][1]+1,dp[i-1][0]+2));
        }
    }
    cout<<min(dp[mxn][0],dp[mxn][1]+1)<<endl;
}
int main(){
    m=read(),n=read();
    if(m>=n){cout<<m-n<<endl;return 0;}
    else DP(); 
    return 0;
}