Codeforces 744C. Hongcow Buys a Deck of Cards（状压DP）

　　这题的难点在于状态的设计

　　首先显然是个状压，需要一维表示卡的状态，另一维如果设计成天数，难以知道当前的钱数，没法确定是否能够购买新的卡，如果设计成钱数，会发现状态数过多，空间与时间都无法承受。但是可以发现，如果没有买卡的钱会因当前卡数变化而变化这个条件的话，买卡的钱是一定的，而我们因拥有卡而省的钱不会超过120（1+2+3+...+15）。所以可以将状态设计成f[i][j]表示卡的状态为i，省了j个红币，能省多少个蓝币。

　　然后就结束了...

　　注意所有下标为状态的数组的大小T T...

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

using namespace std;

const int maxn=, inf=1e9;

int n, st, sumr, sumb, ans;

int r[maxn], b[maxn], cntr[<<], cntb[<<], f[<<][];

char ch[maxn][];

inline void read(int &k)

{

    int f=; k=; char c=getchar();

    while(c<'' || c>'') c=='-'&&(f=-), c=getchar();

    while(c<='' && c>='') k=k*+c-'', c=getchar();

    k*=f;

}

int main()

{

    read(n); st=(<<n)-;

    for(int i=;i<=n;i++)scanf("%s", ch[i]), read(r[i]), read(b[i]), sumr+=r[i], sumb+=b[i];

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

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

            if(i&(<<(j-)))

                cntr[i]+=(ch[j][]=='R')?:, cntb[i]+=(ch[j][]=='B')?:;

    memset(f,-,sizeof(f)); f[][]=;

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

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

            if(f[i][j]!=-)

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

                    if(!(i&(<<(k-))))

                    {

                        int numr=min(r[k], cntr[i]), numb=min(b[k], cntb[i]);

                        f[i|(<<(k-))][j+numr]=max(f[i|(<<(k-))][j+numr], f[i][j]+numb);

                    }

    ans=inf;

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

        if(f[st][i]!=-)

            ans=min(ans, max(sumr-i, sumb-f[st][i]));

    printf("%d\n", ans+n);

}

巴特西

Codeforces 744C. Hongcow Buys a Deck of Cards（状压DP）

最新文章

热门文章