这道题像了很长时间才想明白了思路，没有明显的边界状态，状态转移也不能仅仅依靠一个dp数组。
dp[i][j][k][l] 代表四堆糖果分别拿了ijkl个还能拿到的最多糖果对数（是还能拿到，不算已经拿到的），can数组存储题目输入给出的糖果，top数组表示四堆糖果都拿到了第几个（就是为了简化代码），递推边界为count_bits(S) == 5 或者所有的糖果都被拿光 count_bits计算的是一个数二进制有多少位是1
1 #include<cstdio> 2 #include<cmath> 3 #include<cstring> 4 #include<algorithm> 5 #include<map> 6 #include<set> 7 #include<vector> 8 #include<iostream> 9 #define PB push_back 10 #define POB pop_back 11 #define PII pair<int, int> 12 #define PDD pair<double, double> 13 #define rep(i, a, b) for(int i = a ; i < b ; i++) 14 #pragma comment(linker, "/STACK:1024000000,1024000000") 15 #ifdef WIN32 16 #define INT64 "%I64d" 17 #define UINT64 "%I64u" 18 #else 19 #define INT64 "%lld" 20 #define UINT64 "%llu" 21 #endif 22 typedef long long LL; 23 typedef unsigned long long ULL; 24 using namespace std; 25 const int maxn = 41; 26 int dp[maxn][maxn][maxn][maxn]; 27 int can[maxn][4]; int top[5]; 28 int n; 29 inline int count_bits(int x){ 30 x = (x & 0x55555555) + ((x & 0xaaaaaaaa) >> 1); 31 x = (x & 0x33333333) + ((x & 0xcccccccc) >> 2); 32 x = (x & 0x0f0f0f0f) + ((x & 0xf0f0f0f0) >> 4); 33 x = (x & 0x00ff00ff) + ((x & 0xff00ff00) >> 8); 34 x = (x & 0x0000ffff) + ((x & 0xffff0000) >> 16); 35 return x; 36 } 37 int DP(int S) { //S 表示篮子里的糖果 38 int& cnt = dp[top[0]][top[1]][top[2]][top[3]]; 39 if(cnt != -1) return cnt; 40 if(count_bits(S) == 5) return cnt = 0; 41 for(int i = 0 ; i < 4 ; i++) { 42 if(top[i] >= n) continue; 43 top[i]++; 44 int t = 1 << can[top[i]][i]; 45 if(S & t) cnt = max(cnt, DP(S & (~t)) + 1); 46 else cnt = max(cnt, DP(S | t)); 47 top[i]--; 48 } 49 return cnt = max(cnt, 0); 50 } 51 int main() 52 { 53 while(scanf("%d", &n) == 1 && n) { 54 memset(dp, -1, sizeof dp); 55 memset(top, 0, sizeof top); 56 for(int i = 1 ; i <= n ; i++) 57 for(int j = 0 ; j < 4 ; j++)scanf("%d", &can[i][j]); 58 printf("%d ", DP(0)); 59 } 60 return 0; 61 }