在状态复杂,信息多且数据小的情况下可以选择考虑记忆化搜索.这题我就做的很zz,一开始已知想打一个dp, 不过太麻烦了.看了解题报告之后才发现记忆化搜索这么简单
#include<iostream> #include<cstring> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fod(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int N=40+5,M=20+5; int dp[N][N][N][N],top[5],pile[5][N], n; bool Hash[N]; void Init() { fo(i,0,n-1) fo(j,0,3) scanf("%d",&pile[j][i]); memset(dp,-1,sizeof(dp)); memset(top,0,sizeof(top)); memset(Hash,0,sizeof(Hash)); } int dfs(int count, bool Hash[]) { if (dp[top[0]][top[1]][top[2]][top[3]] != -1) return dp[top[0]][top[1]][top[2]][top[3]]; if (count == 5) return dp[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 color = pile[i][top[i]]; top[i] += 1; if (Hash[color]) { Hash[color] = false; ans = max(ans, dfs(count-1, Hash) + 1); Hash[color] = true; } else { Hash[color] = true; ans = max(ans, dfs(count+1, Hash)); Hash[color] = false; } top[i] -= 1; } return dp[top[0]][top[1]][top[2]][top[3]] = ans; } int main() { while(scanf("%d",&n)&&n) { Init(); printf("%d\n",dfs(0,Hash)); } return 0; }