思路:d[a][b][c][d]表示从已经第一个篮子取了a颗糖,第二个取了b颗糖,第三个取了c颗糖,第四个取了d颗糖最多还能够获得多少糖果。首先明白一个问题:如果能分别取a,b,c,d个,不论如何取,最后篮子中剩余的糖果颜色和个数都是一样的。那么一旦搜索到一个已经被搜索过得状态,直接返回即可,没必要继续搜索。
AC代码:
#include<cstdio> #include<algorithm> #include<cstring> #include<utility> #include<string> #include<iostream> #include<map> #include<set> #include<vector> #include<queue> #include<stack> using namespace std; #define eps 1e-10 #define inf 0x3f3f3f3f #define PI pair<int, int> const int maxn = 40 + 2; int cand[4][maxn], n; int d[maxn][maxn][maxn][maxn]; int top[4], bit[30]; void init() { bit[0] = 1; for(int i = 1; i < 22; ++i) bit[i] = bit[i-1] * 2; } int dfs(int color, int cnt) { if(d[top[0]][top[1]][top[2]][top[3]] != -1) return d[top[0]][top[1]][top[2]][top[3]]; if(cnt == 5) return d[top[0]][top[1]][top[2]][top[3]] = 0; int ans = 0; for(int i = 0; i < 4; ++i) { if(top[i] >= n) continue; int col = ++top[i]; col = bit[cand[i][col]]; if(col & color) { //篮子中已经右该颜色 int a = 1 + dfs(color - col, cnt - 1); ans = max(ans, a); } else { int a = dfs(color + col, cnt + 1); ans = max(ans, a); } top[i]--; } return d[top[0]][top[1]][top[2]][top[3]] = ans; } int main() { init(); while(scanf("%d", &n) == 1 && n) { memset(d, -1, sizeof(d)); memset(top, 0, sizeof(top)); for(int i = 1; i <= n; ++i) for(int j = 0; j < 4; ++j) scanf("%d", &cand[j][i]); printf("%d\n", dfs(0, 0)); } return 0; }
如有不当之处欢迎指出!