Problem Statement |
|
|
You are given three integers: a, b and c. Convert each of them into their binary representations with no leading zeroes. Let x be the number of binary digits in the longest of the three. Add leading zeroes to the others until all of them have exactly x digits. Transform a, b and c into a', b' and c', such that a'+b'=c', by optionally reordering the digits within each number. Leading zeroes are allowed. If there are several ways to do this, use the one that minimizes c'. For example, let a = 7, b = 6 and c = 9. In binary notation, a = 111, b = 110 and c = 1001. We add leading zeroes to a and b so that all of them have exactly four digits: a = 0111, b = 0110, c = 1001. Now, if we reorder the digits within each number to get a' = 0111, b' = 0011 and c' = 1010, we satisfy a' + b' = c' (7 + 3 = 10). There is another way to do this as well (7 + 5 = 12), but this is the way that minimizes c'. You are given ints a, b and c. Return the minimal possible value of c'. If there is no solution, return -1. |
|
abc(binary)中1的个数固定，求a+b=c组合中c的最小值。
因为固定，所以可以考虑使用abc可使用1的个数做状态。首先是分层，从低位向高位，其次考虑进位，因此有5个状态表示量。
方程是f(n,a,b,c,d)d代表进位。ab各两种取法，决定了c和d。所以计算出f(n-1)最小值*2+c就是当前f(n)的最小值。顺便提一下，vc2005支持64位整数，使用的是longlong，而vc6还不支持。但是vc2005默认开堆栈居然只有1M！害得我莫名其妙stackoverflow了N久。
代码功能暂时挂了，就这样吧。
#define INF (1e60)
#define MAX (1 << 29)
#define MIN (-MAX)
#define INFLL (10000000000LL)
#define MAX_N (15)
#define min(x, y) ( x < y ? x : y )
#define max(x, y) ( x > y ? x : y )
#define rep(i, n) for ( i = 0; i < n; i ++ )
typedef long long LL;
class BinarySum
{
LL dp[32][32][32][32][2];
int ones ( int n )
{
return ( n > 0 ? ( n & 1 ) + ones ( n >> 1 ) : 0 );
}
int digit ( int n )
{
return ( n > 0 ? 1 + digit ( n >> 1 ) : 0 );
}
LL get ( int n, int a, int b, int c, int p )
{
if ( a < 0 || a > n )
return INFLL;
if ( b < 0 || b > n )
return INFLL;
if ( c < 0 || c > n )
return INFLL;
LL &res = dp[n][a][b][c][p];
if ( res != -1 )
return res;
res = INFLL;
if ( n == 0 )
{
if ( a == 0 && b == 0 && c == 0 && p == 0 )
res = 0;
else
res = INFLL;
//printf ( "%d %d %d %d %d %lld/n", n, a, b, c, p, res );
return res;
}
int i, j, k;
rep ( i, 2 ) rep ( j, 2 )
{
k = i + j + p;
LL temp = get ( n - 1, a - i, b - j, c - ( k & 1 ), k >> 1 );
temp = temp * 2 + ( k & 1 );
res = min ( res, temp );
}
//printf ( "%d %d %d %d %d %lld/n", n, a, b, c, p, res );
return res;
}
public:
int rearrange ( int a, int b, int c )
{
int la, lb, lc;
la = ones ( a ), lb = ones ( b ), lc = ones ( c );
int l = max ( max ( digit ( a ), digit ( b ) ), digit ( c ) );
memset ( dp, 0xff, sizeof ( dp ) );
LL res = get ( l, la, lb, lc, 0 );
if ( res == INFLL )
return -1;
else
return int ( res );
}
};