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