UVA 10118 简单DP

2019-11-06 08:51:50

字体：大中小

来源：转载

供稿：网友

题意

四堆糖果，有一个容量为5的篮子，每次可以从糖果堆顶端取一个糖果，若篮子中恰好有相同颜色的糖果，则将该糖果装入口袋中。问最多可以取多少个糖果。

题解

设dp[i][j][k][m]为四堆分别取了i,j,k,m个后，最多还能取多少个糖果。使用hash标记篮子中有的糖果颜色，DFS记忆化搜索即可得解。

代码

#include <iostream>#include<cstdio>#include<algorithm>#include<cstring>using namespace std;int mp[50][5];int dp[50][50][50][50];int top[50];int n;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=mp[top[i]][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)!=EOF){ if(n==0) break; for(int i=0;i<n;i++){ for(int j=0;j<4;j++){ scanf("%d",&mp[i][j]); } } memset(dp,-1,sizeof(dp)); memset(top,0,sizeof(top)); bool hash[30]; memset(hash,false,sizeof(hash)); PRintf("%d/n",dfs(0,hash)); } return 0;}

上一篇：经典算法——冒泡排序法

下一篇：区别（类、成员、属性、对象、方法）