题目大意:有4堆糖果,每堆有n个,有一只最多能容5个糖果的篮子。现在,要把糖果放到篮子里,如果篮子中有相同颜色的糖果,放的人就可以拿到自己的口袋。如果放的人足够聪明,问他最多能得到多少对糖果。
题目分析:很显然的多阶段决策。定义dp(a,b,c,d)为每堆糖果分别拿掉a、b、c、d块之后最多能获得得糖果对数。则决策有4个,以第一堆为例,状态转移方程为:dp(a,b,c,d)=dp(a+1,b,c,d) (如果拿掉第一堆的第a+1个不会产生相同颜色)、dp(a,b,c,d)=dp(a+1,b,c,d)+1 (如果拿掉第一堆的第a+1个会产生相同颜色)。
在没做这道题之前从没想过记忆化搜索还能这么写!。
代码如下:
# include<iostream>
# include<cstring>
# include<cstdio>
# include<vector>
# include<set>
# include<map>
# include<list>
# include<string>
# include<cmath>
# include<queue>
# include<stack>
# include<algorithm>
# define LL long long using namespace std; const int INF=0x7fffffff; int dp[41][41][41][41],top[4];
int nums[41][4],n;
bool vis[25]; int DP(int k)
{
int &ans=dp[top[0]][top[1]][top[2]][top[3]];
if(ans!=-1) return ans;
ans=0;
if(k>=5) return ans;
for(int i=0;i<4;++i){
if(top[i]==n) continue;
++top[i];
if(vis[nums[top[i]][i]]){
vis[nums[top[i]][i]]=false;
ans=max(ans,DP(k-1)+1);
vis[nums[top[i]][i]]=true;
}else{
vis[nums[top[i]][i]]=true;
ans=max(ans,DP(k+1));
vis[nums[top[i]][i]]=false;
}
--top[i];
}
return ans;
} int main()
{
while(scanf("%d",&n)&&n)
{
for(int i=1;i<=n;++i)
for(int j=0;j<4;++j)
scanf("%d",&nums[i][j]);
memset(vis,false,sizeof(vis));
memset(dp,-1,sizeof(dp));
memset(top,0,sizeof(top));
printf("%d\n",DP(0));
}
return 0;
}