在这里插入图片描述
UVA10118
定义：
$dp[a][b][c][d]$为第0列取了$a$颗糖果，第1列$b$颗，第二列$c$颗，第三列$d$后剩下的糖果还能最多再装进口袋多少个。那么答案就是$dp[0][0][0][0]$，即考虑所有糖果。$Candies[i][j]$表示第$i$行第$j$列的糖果颜色。
初始化：

表示未计算过
转移方程：

$IsPair(Cow,Raw)$表示拿了$Candies[Col][Raw]$后是否能和篮子中的糖果配对，并放入口袋中。
AC代码：
代码中以$Raw[0]$表示$a$，$Raw[1]$表示$b$，$Raw[2]$表示$c$，$Raw[3]$表示$d$，以减少代码量。采用二进制压缩的方式表示当前篮子中的糖果集合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
#define scanf scanf_s
int N;
int Candies[41][4];
int dp[41][41][41][41];
bool Input() {
	cin >> N; 
	if (!N) {
		return false;
	}
	for (int i = 1; i <= N; ++i) {
		for (int j = 0; j < 4; ++j) {
			cin >> Candies[i][j];
		}
	}
	return true;
}
//获取篮子中糖果的数量
int getNumber(int CandiesSet) {
	int&& Number = 0;
	while (CandiesSet) {
		Number += (CandiesSet & 1);
		CandiesSet >>= 1;
	}
	return Number;
}
int DP(int Raw[4], int CandiesSet/*篮子中糖果的集合*/) {
	int& Ans = dp[Raw[0]][Raw[1]][Raw[2]][Raw[3]];
	//如果计算过就直接返回
	if (~Ans) {
		return Ans;
	}
	//糖果数量大于4就说明篮子满了，返回极小值
	if (getNumber(CandiesSet) > 4) {
		return Ans = 0xcfcfcfcf;
	}
	//最少装0个
	Ans = 0;
	//枚举a+1，b+1，c+1，d+1
	for (int i = 0; i < 4; ++i) {
		//如果到了最后一列最跳过，不能再往下了
		if (Raw[i] != N) {
			int&& Total = 0;
			//+1
			++Raw[i];
			//向下取的那个糖果
			int&& CurrentCandy = 1 << (Candies[Raw[i]][i] - 1);
			//如果新取的糖果再篮子集合中，则可以配对
			if (CandiesSet & CurrentCandy) {
				++Total;
			}
			//往下DP
			Total += DP(
				Raw,
				//如果新取的糖果在篮子中，就配对成功，集合去点这种糖果，如果没有，就将糖果加入篮子中（异或的开关性）
				CandiesSet ^ CurrentCandy
			);
			//还原Raw[i]，为枚举下一列做准备
			--Raw[i];
			Ans = max(Ans, Total);
		}
	}
	return Ans;
}
int main() {
	ios::sync_with_stdio(false);
	while (Input()) {
		memset(dp, -1, sizeof(dp));
		int Raw[4] = { 0,0,0,0 };
		cout << DP(Raw, 0) << endl;
	}
	return 0;
}