M_sea

洛谷1633 二进制
Luogu算法自然想到用$f[i] [a] [b] [c] [d] [0/1$]来作为状态。其中i代表前i位,a、...
扫描右侧二维码阅读全文
22
2017/10

洛谷1633 二进制

Luogu

算法

自然想到用$f[i] [a] [b] [c] [d] [0/1$]来作为状态。其中i代表前i位,a、b、c分别代表X、Y、Z中有a、b、c个1,0代表这一位不进位,1代表进位。那么$f[i] [a] [b] [c] [0/1]$就代表该状态下最小的Z。

首先考虑$f[i] [a] [b] [c] [0]$的转移。
首先,若这一位X、Y都选0,那么Z这一位也是0,且没有进位:

  0……
+ 0……
-------
  0……

得$f[i+1][a][b][c][0]=min(f[i+1][a][b][c][0],f[i][a][b][c][0])$
其次,若X和Y这一位都要选,那么Z这一位就是0,但是要进位:

  1……
+ 1……
-------
 10……

则$f[i+1][a+1][b+1][c][1]=min(f[i+1][a+1][b+1][c][1],f[i][a][b][c][0]+(1<<i))$
然后,若X选Y不选,那么Z这一位就是1,且不进位:

  1……
+ 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<<(i-1)))$
最后,若X不选Y选,那么同上。

  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<<(i-1)))$

然后考虑$f[i] [a] [b] [c] [1]$的转移。
首先,若这一位X、Y都选0,那么Z这一位是1(有进位),且没有进位:

  0……
+ 0……
-------
  1……

得$f[i+1][a][b][c+1][0]=min(f[i+1][a][b][c+1][0],f[i][a][b][c][1])$
其次,若X和Y这一位都要选,那么Z这一位还是1,而且要进位:

  1……
+ 1……
-------
 11……

则$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<<i))$
然后,若X选Y不选,那么Z这一位就是0,且进位:

  1……
+ 0……
-------
 10……

则$f[i+1][a+1][b][c][1]=min(f[i+1][a+1][b][c][1],f[i][a][b][c][1]+(1<<(i-1)))$
最后,若X不选Y选,那么同上。

  0……
+ 1……
-------
 10……

则$f[i+1][a][b+1][c][1]=min(f[i+1][a][b+1][c][1],f[i][a][b][c][1]+(1<<(i-1)))$

注意判断无解,方法是把没有的状态置为$+\infty$。
边界为$f[1] [0] [0] [0] [0]=0$。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;
int l;
inline int Bit(int k) //求二进制1的个数顺便更新长度
{
    int s=0,tl=0;
    for (;k;k>>=1,++tl) s+=k&1;
    if (tl>l) l=tl;
    return s;
}
inline int read() //读优
{
    int X=0,w=1; char ch=getchar();
    while (ch<'0'||ch>'9') { if (ch=='-') w=-1; ch=getchar(); }
    while (ch>='0'&&ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
    return X*w;
}
inline void GetMin(int& a,int b) { if (b<a) a=b; } //就是a=min(a,b)的功能
int f[40][40][40][40][2]; //DP数组
int main()
{
    int t; t=read();
    while (t--) { //t组数据
        l=0;
        int A=read(),B=read(),C=read();
        A=Bit(A),B=Bit(B),C=Bit(C); //数据+处理
        memset(f,0x7f,sizeof(f)); //置INF
        int INF=f[1][0][0][0][0]; //记录一下INF
        f[1][0][0][0][0]=0; //边界
        for (re int i=1;i<=l;i++) //DP
            for (re int a=0;a<=A;a++)
                for (re int b=0;b<=B;b++)
                    for (re int c=0;c<=C;c++) {
                        int t;
                        t=f[i][a][b][c][0];
                        if (t<INF) { //状态存在
                            GetMin(f[i+1][a][b][c][0],t);
                            GetMin(f[i+1][a+1][b+1][c][1],t+(1<<i));
                            GetMin(f[i+1][a+1][b][c+1][0],t+(1<<(i-1)));
                            GetMin(f[i+1][a][b+1][c+1][0],t+(1<<(i-1)));
                        }
                        t=f[i][a][b][c][1];
                        if (t<INF) { //状态存在
                            GetMin(f[i+1][a][b][c+1][0],t);
                            GetMin(f[i+1][a+1][b+1][c+1][1],t+(1<<i));
                            GetMin(f[i+1][a+1][b][c][1],t+(1<<(i-1)));
                            GetMin(f[i+1][a][b+1][c][1],t+(1<<(i-1)));
                        }
                    }
        if (f[l+1][A][B][C][0]!=INF) printf("%d\n",f[l+1][A][B][C][0]); //有解就输出
        else printf("-1\n"); //无解
    }
    return 0;
}
最后修改:2018 年 11 月 30 日 09 : 33 PM

发表评论