BZOJ3107 CQOI2013二进制A+B（动态规划）

时间：2022-12-23 10:16:25

　　显然答案只与a、b、c中各自1的个数及位数有关。a、b只考虑前i位怎么填时，c最多在第i+1位上为1，而第i+1位及之后的a、b怎么填都不会对前i位造成影响。于是设f[n][i][j][k][0/1]表示只考虑前n位，a用i个1，b用j个1，c用k个1，且c的第n+1位为0/1时的最小值。转移时枚举下一位a和b各自填0还是1即可。注意230是有31位的，防止爆int。本来输出的时候是三目运算符的结果发现-1会输出成232-1。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define N 32

#define int unsigned int

#define inf ((1<<31)-1)

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int a,b,c,n,f[N][N][N][N][];

inline void update(int &x,int y){x=min(x,y);}

signed main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj3107.in","r",stdin);

    freopen("bzoj3107.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    a=read(),b=read(),c=read();

    int t=,cnt=;

    while (a) t++,cnt+=a&,a>>=;

    n=max(n,t);a=cnt;

    t=,cnt=;

    while (b) t++,cnt+=b&,b>>=;

    n=max(n,t);b=cnt;

    t=,cnt=;

    while (c) t++,cnt+=c&,c>>=;

    n=max(n,t);c=cnt;

    for (int i=;i<=n;i++)

        for (int j=;j<=a;j++)

            for (int k=;k<=b;k++)

                for (int l=;l<=c;l++)

                f[i][j][k][l][]=f[i][j][k][l][]=inf;

    f[][][][][]=;

    for (int i=;i<n;i++)

        for (int j=;j<=min(a,i);j++)

            for (int k=;k<=min(b,i);k++)

                for (int l=;l<=min(c,i+);l++)

                {

                    update(f[i+][j][k][l][],min(f[i][j][k][l][],f[i][j][k][l][]));

                    update(f[i+][j+][k][l+][],f[i][j][k][l][]+(<<i));

                    update(f[i+][j][k+][l+][],f[i][j][k][l][]+(<<i));

                    update(f[i+][j+][k][l][],f[i][j][k][l][]+(<<i));

                    update(f[i+][j][k+][l][],f[i][j][k][l][]+(<<i));

                    if (i+<n) update(f[i+][j+][k+][l+][],min(f[i][j][k][l][],f[i][j][k][l][])+(<<i+));

                }

    if (f[n][a][b][c][]==inf) cout<<-;

    else cout<<f[n][a][b][c][];

    return ;

}

相关文章