P4574 [CQOI2013]二进制A+B

传送门

数位DP

考虑从右边最小的一位，一位一位填数，填到最大一位

对于 a' b' 各可填 0 或 1

但是发现如果 a' b' 都填一，更高一位会进1

所以要多一维表示更高一位是否为 1

那么设 f [ i ] [ j ] [ k ] [ l ] [ 0/1 ] 表示填到第 i 个数，a' 填了 j 个 1，b' 填了 k 个 1，c' 有了 l 个1，更高一位(第i+1位)是否有1

那么就可以考虑转移了

转移还是看代码吧(前方高能)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
long long f[37][37][37][37][2],ans,inf;//注意要开long long
int mxa,mxb,mxc,mx;//a,b,c的位数和最大位数
int main()
{
    memset(f,63,sizeof(f)); ans=inf=f[2][3][3][3][0];//初始化
    int a,b,c,n;
    cin>>a>>b>>c;
    n=max(a,max(b,c));

    while(a) mxa+=a&1,a>>=1;
    while(b) mxb+=b&1,b>>=1;
    while(c) mxc+=c&1,c>>=1;
    while(n) mx++,n>>=1;
    //计算位数

    f[0][0][0][0][0]=0;
    //前方高能
    for(int i=0;i<mx;i++)//第i位，现在要填第i+1位
    for(int j=0;j<=min(i,mxa);j++)//a'的1的数量
    for(int k=0;k<=min(i,mxb);k++)//b'的1的数量
    for(int l=0;l<=min(l,mxc);l++)//c'的1的数量
    for(int x=0;x<=1;x++)//此位a'是否填1
    for(int y=0;y<=1;y++)//此位b'是否填1
    for(int z=0;z<=1;z++)//此位是否有进位
    {
        if(x+y+z&1) /*如果加起来为会使c'多一个1*/ f[i+1][j+x][k+y][l+1][x+y+z>>1]=min( f[i+1][j+x][k+y][l+1][x+y+z>>1] , f[i][j][k][l][z]+(1<<i) );
        else /*否则*/ f[i+1][j+x][k+y][l][x+y+z>>1]=min( f[i+1][j+x][k+y][l][x+y+z>>1] , f[i][j][k][l][z] );
    }//神奇的7层循环

    printf("%lld",f[mx][mxa][mxb][mxc][0]==inf ? -1 : f[mx][mxa][mxb][mxc][0]);
    return 0;
}

P4574 [CQOI2013]二进制A+B

推荐阅读