一道数位dp题，状态有点复杂但是不难

补个范围：

题目大意：
给你三个数:a,b,c
你可以对这三个数的二进制进行任意排列使得最终满足：c=a+b
求最小的满足条件的c，如果没有输出-1
这道题，我们考虑先计算出a,b,c各种的二进制中有多少个"1",分别设为：A,B,C
在算出三个数中二进制长度最长的，设为n
那么，现在题目就相当于：
分别用A,B,C个1凑出长度为n的三个二进制数（允许前导0）满足上述和的关系，且要求c最小

于是我们就可设int 表示，我们还剩i位，C剩j个1,A剩k个1,B剩t个1能凑出满足条件的最小的数来

但，我们注意到，题目是“加法”，于是自然而然的产生了一种情况——进位，如果我们dp这么设的话，是无法保证答案正确的，所以我们再开一位：表示我们还剩i位，C剩j个1,A剩k个1,B剩t个1并且我们是否要向前1位进1（因为最大情况就是1+1+1(本身两个1加上后面进的1))

一开始有：

那么，我们就来考虑转换：
如果，我们现在不向前一位进1，那么有如下情况：
1.A,B都是0，且后一位不进1=>现在这一位就是0
2.A,B都是0，且后一位进1=>现在这一位就是1
3.A,B有一个是1，且后一位不进1=>现在这一位就是1
于是我们有转移方程：
(当然，如果j/k/t等于0的话，那么j/k/t就不存在需要-1的情况了)
同理，我们有向前一位进1的转移方程：
这样，我们就可以直接推出所有的dp的值了
按照意义，答案就是
复杂度
可以通过此题
代码（我打的记搜，2333）：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=50,inf=1e15;
long long sav[N];
long long dp[N][N][N][N][2];
bool vis[N][N][N][N][2];
inline int dfs(int now,int C,int A,int B,bool ned){
    if(!now){
       if(C==0&&A==0&&B==0&&ned==0){
           return 0;
       }
       return inf;
    }
    if(vis[now][C][A][B][ned]){
        return dp[now][C][A][B][ned];
    }
    vis[now][C][A][B][ned]=1;
    int res=inf;
    if(ned){
        //0
        if(A&&B){
            res=min(res,dfs(now-1,C,A-1,B-1,0));
        }
        if(A){
            res=min(res,dfs(now-1,C,A-1,B,1));
        }
        if(B){
            res=min(res,dfs(now-1,C,A,B-1,1));
        }
        //1
        if(C){
            if(A&&B){
                res=min(res,dfs(now-1,C-1,A-1,B-1,1)+sav[now]);
            }
        }
    }else{
        //0
        res=min(res,dfs(now-1,C,A,B,0));
        //1
        if(C){
            res=min(res,dfs(now-1,C-1,A,B,1)+sav[now]);
            if(A){
                res=min(res,dfs(now-1,C-1,A-1,B,0)+sav[now]);
            }
            if(B){
                res=min(res,dfs(now-1,C-1,A,B-1,0)+sav[now]);
            }
        }
    }
    return dp[now][C][A][B][ned]=res;
}
signed main(){
    sav[1]=1;
    for(int i=2;i<=49;++i){
        sav[i]=(sav[i-1]<<1);
    }
    long long a,b,c;
    scanf("%lld%lld%lld",&a,&b,&c);
    int A=0,B=0,C=0,tot=0,tol=0;
    while(a){
        A+=(a&1);a>>=1;++tot;
    }
    while(b){
        B+=(b&1);b>>=1;++tol;
    }
    tot=max(tot,tol),tol=0;
    while(c){
        C+=(c&1);c>>=1;++tol;
    }
    tot=max(tot,tol);
    memset(dp,0x3f3f,sizeof(dp));
    dfs(tot,C,A,B,0);
    if(dp[tot][C][A][B][0]>=sav[tot+1]){
        puts("-1");
    }else{
        printf("%lld",dp[tot][C][A][B][0]);
    }
    return 0;
}