数位dp
设f[ i ][ a ][ b ][ c ][ 0/1 ]表示在第 n-i 位，A、B、C各贡献了a、b、c个1，是否需要进位的情况下，c的最小值
然后对于8种情况枚举
#include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef long long ll; template <typename T> inline T min(T &a,T &b) {return a<b ?a:b;} template <typename T> inline int find(T a) {int res=0; for(;a;a>>=1)++res; return res;} //计算位数 template <typename T> inline int cont(T x) {int res=0; for(;x;x&=(x-1))++res; return res;} //计算二进制下1的个数 ll f[33][33][33][33][2],ans,inf; int main(){ memset(f,63,sizeof(f)); inf=ans=f[0][0][0][0][0]; int A,B,C,mxd; scanf("%d%d%d",&A,&B,&C); mxd=max(max(find(A),find(B)),find(C)); A=cont(A),B=cont(B),C=cont(C); f[0][0][0][0][0]=0; for(int i=0;i<=mxd;++i) for(int a=0;a<=min(i+1,A);++a) for(int b=0;b<=min(i+1,B);++b) for(int c=0;c<=min(i+1,C);++c){ //8种枚举 f[i+1][a][b][c][0]=min(f[i+1][a][b][c][0],f[i][a][b][c][0]<<1); f[i+1][a+1][b][c+1][0]=min(f[i+1][a+1][b][c+1][0],f[i][a][b][c][0]<<1|1); f[i+1][a][b+1][c+1][0]=min(f[i+1][a][b+1][c+1][0],f[i][a][b][c][0]<<1|1); f[i+1][a+1][b+1][c][0]=min(f[i+1][a+1][b+1][c][0],f[i][a][b][c][1]<<1); f[i+1][a][b][c+1][1]=min(f[i+1][a][b][c+1][1],f[i][a][b][c][0]<<1|1); f[i+1][a][b+1][c][1]=min(f[i+1][a][b+1][c][1],f[i][a][b][c][1]<<1); f[i+1][a+1][b][c][1]=min(f[i+1][a+1][b][c][1],f[i][a][b][c][1]<<1); f[i+1][a+1][b+1][c+1][1]=min(f[i+1][a+1][b+1][c+1][1],f[i][a][b][c][1]<<1|1); } for(int i=0;i<=mxd;++i) ans=min(ans,f[i][A][B][C][0]); if(ans==inf) printf("-1"); else printf("%lld",ans); return 0; }