UVA10118 Free Candies 题解

题目链接：UVA10118 Free Candies

题意：

cxy 正在玩一个游戏。她想要赢得尽可能多的糖果。 有 \(4\) 堆糖果，每堆包含 \(N\) 个糖果。cxy 被给予一个篮子，最多可以容纳 \(5\) 个糖果。每次，她将一颗糖果放在一堆的顶部放入篮子中，如果篮子中有两颗相同颜色的糖果，她可以将它们都拿出篮子，放入自己的口袋。当篮子已满且篮子中没有两颗相同颜色的糖果时，游戏结束。如果游戏完美进行，游戏结束时堆中将没有剩余糖果。 例如，cxy 可能会这样玩游戏\((N=5)\)：

注意，不同的数字表示不同的颜色，共有 \(20\) 种颜色，编号为 \(1\) 到 \(20\) 。 "看起来很难..." cxy 非常困惑。

她最多能带回家多少对糖果？

输入格式：

输入将包含不超过 \(10\) 个测试用例。每个测试用例以包含一个整数 \(n(1 \leq n \leq 40)\) 的行开始，表示堆的高度。接下来的 \(n\) 行中，每行包含四个整数\(x_{i_1}, x_{i_2}, x_{i_3}, x_{i_4}\)（取值范围为 \(1\) 到 \(20\) ），每个整数表示相应糖果的颜色。包含 \(n=0\) 的测试用例将终止输入，你不应对该用例给出答案。

输出格式：

对于每个测试用例，输出小聪明的小孩最多能带回家的糖果对数。每个测试用例输出一行。

考虑反向dp，也就是从结束状态往开始状态推，并设 \(f(k,i,j,c)\) 表示每个列的剩余数的个数。

实现也是一个难点吧，首先dp肯定是用 dfs 的，然后篮子里有啥可以用状压维护。

时间复杂度 \(\mathcal{o}(2^9\times n^4)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define popc(x) __builtin_popcountll(x)
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(45))

int n,d[N][4],f[N][N][N][N];
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];
    if(popc(now) > 4) return f[k][i][j][c] = -INF;
    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 ^= (1 << (d[1 + top[o]++][o] - 1));
        tot += dfs(top, now);
        now ^= (1 << (d[--top[o] + 1][o] - 1));
        up(f[k][i][j][c], tot);
    }
    return f[k][i][j][c];
}
void solve()
{
    memset(f, -1, sizeof(f));
    for(int k = 1; k <= n; k++)
        for(int i = 0; i < 4; i++) cin >> d[k][i];
    int ori[4] = {0,0,0,0}; cout << dfs(ori, 0) << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    while(cin >> n && n) solve();
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/Sata-moto/solution-uva10118