Codeforces Round #295 (Div. 2) B. Two Buttons (DP)

题意:有两个正整数\(n\)和\(m\),每次操作可以使\(n*=2\)或者\(n-=1\),问最少操作多少次使得\(n=m\).
题解:首先,若\(n\ge m\),直接输出\(n-m\),若\(2*n>=m\),分\(m\)的奇偶判断一下,如果是奇数就输出\(n-(m+1)/2+2\),是偶数就输出\(n-m/2+1\).否则我们就需要用dp来求解,因为是求最小值,所以先初始化将所有值设为\(INF\),\(dp[i]\)表示从\(n\)到\(m\)的操作次数最少的最优解,首先需要更新\([1,n]\)的状态,这个不难写,\(dp[i]=dp[i+1]+1\),然后我们就可以从\(1\)开始枚举到\(m\),而我们当前的状态\(dp[i]\)可以更新后面的状态\(dp[i*2]\),这步应该不难想,这儿的难点是我们需要更新一些奇数的状态,比如\(n=2\),我们刚开始可以更新\(dp[4]\),然后到\(n=3\)的时候发现\(3\)只能通过\(4\)更新得到,而\(dp[4]\)由\(dp[2]\)更新过了,所以我们可以通过\(dp[4]\)来更新\(dp[3]\),于是每次遍历我们更新两个状态,一个是自己的状态\(dp[i]=min(dp[i],dp[i+1]+1)\),一个是后面的数的状态\(dp[i*2]=min(dp[i*2],dp[i]+1)\).

代码:

int n,m;

int dp[N];

int main() {

    //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    n=read(),m=read();

    if(n>=m){

        printf("%d\n",n-m);

        return 0;

    }

    if(m<=2*n){

        if(m&1){

            int cnt=(m+1)/2;

            printf("%d\n",n-cnt+2);

        }

        else printf("%d\n",n-m/2+1);

        return 0;

    }

    me(dp,INF,sizeof(dp));

    dp[n]=0;

    for(int i=n-1;i>=1;--i) dp[i]=dp[i+1]+1;

    for(int i=1;i<=m;++i){

        dp[i]=min(dp[i],dp[i+1]+1);

        dp[i*2]=min(dp[i*2],dp[i]+1);

    }

    printf("%d\n",dp[m]);

    return 0;

}

巴特西

Codeforces Round #295 (Div. 2) B. Two Buttons (DP)

最新文章

热门文章