题解 UVA10118 【免费糖果 Free Candies】

· · 题解

前言：

\large{}\color {#6495ED} \mathcal{MyBlog}

这是一道难度并不大的DP...

然鹅题解中某些神犇的讲解让我很懵逼0.0..

于是过来发篇题解...

题目大意：

有四堆糖果，每次可以从四堆糖果中拿某堆顶上的一颗糖果，放到袋子里，如果袋子里有两份相同的糖果，那么就可以把那两枚糖果拿到口袋里...如果袋子里糖果数超过5枚，游戏结束，求最多可以拿多少对糖果

题目分析:

首先，我们分析数据规模：N<=40...

似乎用DP处理这道题是可行的...

我们注意到：每次拿糖果都只能拿堆顶糖果...

所以说，剩下哪些糖果没拿，可以转化为四堆中分别剩下糖果的数目..

那么如何表示已经拿走的糖果？

不，已经拿走的糖果我们不需要关心，我们关心袋子里的糖果就好了...

如何处理袋子中的糖果？状态压缩？

使用最裸的方法，我们可以开f[k][i][j][c][S]表示，我们从第一堆糖果中取走了k个，从第二堆中取走了i个，从第三堆中取走了j个，从第四堆中取走了c个，袋子中的糖果种类用二进制压成了S，之后，拿走剩下糖果的最大价值...

很显然，空间爆炸的厉害...

我们考虑优化：

设糖果总集为U，剩下的集合为A，拿走的集合为B，A是B的补集，故若A唯一确定，那么B也唯一确定...又因为B->S是唯一的，所以当我们确定了A时，我们就确定了S...

而显然，k,i,j,c四维可以表示出A，那么S就也被隐式地表达了，我们大可以把它删去，不影响我们记忆化的过程...

故我们设状态f[k][i][j][c]就好...

转移便是转移到分别从每一堆中拿走一个糖果后的状态...

具体细节见代码...

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 44;

int n;
int d[N][4];
int f[N][N][N][N];//从第一堆拿了k个，第二堆拿了i个，第三堆拿了j个，第四堆拿了c个后
                  //从剩下的糖果中拿取而获得的最大价值

//处理某一个数中有多少个1,也就是袋子里有多少糖果 
int count_1(int x)
{
    int num = 0;

    while(x)
    {
        num += ((x & 1) == 0 ? 0 : 1);
        x >>= 1;
    }

    return num;
}

//这里有一个小技巧，dfs传参的时候传数组，可以避免掉手写四种转移 
//top[]代表每一个堆各拿了多少个糖，now表示二进制压缩后的袋子中的糖果情况
int dfs(int top[], int now)
{
    int k = top[0], i = top[1], j = top[2], c = top[3];

    //是否处理过了 
    if(f[k][i][j][c] != -1)
        return f[k][i][j][c];

    //如果有5个不一样的糖果，那么就不能装糖果了，把答案设为极小值返回 
    if(count_1(now) > 4)
        return f[k][i][j][c] = 0xcfcfcfcf;

    f[k][i][j][c] = 0;
    for(int o = 0; o < 4; o++)
        if(top[o] != n)
        {
            int tot = 0;
            //能否“消掉”袋子里的糖 
            if(now & (1 << (d[top[o] + 1][o] - 1)))
                tot = 1;

            //转移 （直接修改now后传到下一次DFS里可以避免计算）
            //这个位运算应该还好理解？ 
            now ^= (1 << (d[1 + top[o]++][o] - 1));
            tot += dfs(top, now);
            now ^= (1 << (d[--top[o] + 1][o] - 1));

            //取最大值 
            f[k][i][j][c] = max(f[k][i][j][c], tot);
        }

    return f[k][i][j][c];
}

int main()
{
    while(scanf("%d", &n) != EOF && n)
    {
        //多测不清空，爆零两行泪 
        memset(f, -1, sizeof(f));

        for(int k = 1; k <= n; k++)
            for(int i = 0; i < 4; i++)
                scanf("%d", &d[k][i]);

        int ori[4] = {0, 0, 0, 0};
        printf("%d\n", dfs(ori , 0));
    }

    return 0;
}

结语：

如果本题解有BUG...

那么...那么...那么...

（随意了）还请私信作者....

END