http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=19440
题意，4堆不同颜色的糖果，每堆N个，从堆上往下拿，放入一个最大装5个糖果的篮子里，如果糖果颜色相同就能将这两个放入自己口袋，问最多能放多少
分析：dp[1][2][3][4]表示取每一堆的第1，2，3，4个的情况，top[i]表示第i堆该取的个数，记忆化搜索
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; const int MAX = 50; int dp[MAX][MAX][MAX][MAX],has_color[MAX],pile[5][MAX],top[5]; int n; int dfs(int cnt) { if(dp[ top[1] ][ top[2] ][ top[3] ][ top[4] ] != -1) return dp[ top[1] ][ top[2] ][ top[3] ][ top[4] ]; if(cnt == 5) //如果已经取了5个，那就是0了 return dp[ top[1] ][ top[2] ][ top[3] ][ top[4] ] = 0; int ans = 0; for(int i = 1; i <= 4; i++) { if(top[i] > n) continue; int color = pile[i][ top[i] ]; top[i] += 1; //下一个 if(has_color[color]) //有一个跟这个颜色相同 { has_color[color] = 0; ans = max(ans, dfs(cnt - 1) + 2);//篮子里还能装cnt-1个，把篮子里那个拿出来 has_color[color] = 1; } else { has_color[color] = 1; ans = max(ans, dfs(cnt + 1)); has_color[color] = 0; } top[i] -= 1; } return dp[ top[1] ][ top[2] ][ top[3] ][ top[4] ] = ans; } int main() { while(scanf("%d", &n) != EOF && n) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= 4; j++) scanf("%d", &pile[j][i]); } memset(has_color, 0, sizeof(has_color)); memset(dp, -1, sizeof(dp)); top[1] = top[2] = top[3] = top[4] = 1; printf("%d ", dfs(0) / 2);//至于这里为什么除以2，以为dfs时暴力了所有假设 是 1 ，2，2，3那么以第二堆为top[2】时能拿两个，以第三堆为top[3]时也能拿两个 } return 0; }