BZOJ 3107 [cqoi2013]二进制a+b (DP)

时间:2021-10-28 10:16:33

3107: [cqoi2013]二进制a+b

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 995  Solved: 444
[Submit][Status][Discuss]

Description

输入三个整数a, b, c,把它们写成无前导0的二进制整数。比如a=7, b=6, c=9,写成二进制为a=111, b=110, c=1001。接下来以位数最多的为基准,其他整数在前面添加前导0,使得a, b, c拥有相同的位数。比如在刚才的例子中,添加完前导0后为a=0111, b=0110, c=1001。最后,把a, b, c的各位进行重排,得到a’, b’, c’,使得a’+b’=c’。比如在刚才的例子中,可以这样重排:a’=0111, b’=0011, c’=1010。
你的任务是让c’最小。如果无解,输出-1。
 

Input

输入仅一行,包含三个整数a, b, c。
 

Output

 
输出仅一行,为c’的最小值。

Sample Input

7 6 9

Sample Output

10

HINT

a,b,c<=2^30

题解:

参考代码:dp[i][j][k][l][m]表示:第I位,第1,2,3个数分别用了几个一,m表示是否有进位:

分类讨论:

  对于m=0的情况: 

   dp[i+1][j+1][k+1][l+1][1]=min(dp[i+1][j+1][k+1][l+1][1],tmp+(1<<i+1));
dp[i+1][j+1][k][l+1][0]=min(dp[i+1][j+1][k][l+1][0],tmp+(1<<i));
dp[i+1][j][k+1][l+1][0]=min(dp[i+1][j][k+1][l+1][0],tmp+(1<<i));
dp[i+1][j][k][l][0]=min(dp[i+1][j][k][l][0],tmp);
 对于m=1的情况:
    dp[i+1][j+1][k+1][l+1][1]=min(dp[i+1][j+1][k+1][l+1][1],tmp+(1<<i+1));
dp[i+1][j][k+1][l][1]=min(dp[i+1][j][k+1][l][1],tmp+(1<<i));
dp[i+1][j+1][k][l][1]=min(dp[i+1][j+1][k][l][1],tmp+(1<<i));
dp[i+1][j][k][l][0]=min(dp[i+1][j][k][l][0],tmp);
 #include<bits/stdc++.h>
using namespace std;
#define clr(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3fll;
ll a,b,c;
ll la,lb,lc,len;
ll dp[][][][][];
void getlen(){len=max(log2(a)+,max(log2(b)+,log2(c)+));}
ll getnum(ll x)
{
ll sum=;
for(int i=;i<;++i) {if( x & (1ll<<i) ) sum++; }
return sum;
}
void work()
{
dp[][][][][]=;
for(ll i=;i<len;++i)
{
for(ll j=;j<=la;++j)
{
for(ll k=;k<=lb;++k)
{
for(ll l=;l<=lc;++l)
{
long long tmp=dp[i][j][k][l][];//枚举最后一位不进位的情况
dp[i+][j+][k+][l+][]=min(dp[i+][j+][k+][l+][],tmp+(<<i+));
dp[i+][j+][k][l+][]=min(dp[i+][j+][k][l+][],tmp+(<<i));
dp[i+][j][k+][l+][]=min(dp[i+][j][k+][l+][],tmp+(<<i));
dp[i+][j][k][l][]=min(dp[i+][j][k][l][],tmp);
tmp=dp[i][j][k][l][];//枚举最后一位进位的情况
dp[i+][j+][k+][l+][]=min(dp[i+][j+][k+][l+][],tmp+(<<i+));
dp[i+][j][k+][l][]=min(dp[i+][j][k+][l][],tmp+(<<i));
dp[i+][j+][k][l][]=min(dp[i+][j+][k][l][],tmp+(<<i));
dp[i+][j][k][l][]=min(dp[i+][j][k][l][],tmp);
}
}
}
}
//cout<<len<<" "<<la<<" "<<lb<<" "<<lc<<endl;
if(dp[len][la][lb][lc][]>=inf) printf("-1\n");
else printf("%d\n",dp[len][la][lb][lc][]);
} int main()
{
scanf("%lld%lld%lld",&a,&b,&c);
getlen(); memset(dp,inf,sizeof dp);
la=getnum(a);lb=getnum(b);lc=getnum(c);
work();
return ;
}