首页 > 搜索 > DFS搜索 > HDU 1514 Free Candies-动态规划-[解题报告] C++
2013
12-12

HDU 1514 Free Candies-动态规划-[解题报告] C++

Free Candies

问题描述 :

Little Bob is playing a game. He wants to win some candies in it – as many as possible.

There are 4 piles, each pile contains N candies. Bob is given a basket which can hold at most 5 candies. Each time, he puts a candy at the top of one pile into the basket, and if there’re two candies of the same color in it ,he can take both of them outside the basket and put them into his own pocket. When the basket is full and there are no two candies of the same color, the game ends. If the game is played perfectly, the game will end with no candies left in the piles.

For example, Bob may play this game like this (N=5):

Note that different numbers indicate different colors, there are 20 kinds of colors numbered 1..20.

‘Seems so hard…’Bob got very much puzzled. How many pairs of candies could he take home at most?

输入:

The input will contain no more than 10 test cases. Each test case begins with a line containing a single integer n(1<=n<=40) representing the height of the piles. In the following n lines, each line contains four integers xi1,xi2,xi3,xi4 (in the range 1..20). Each integer indicates the color of the corresponding candy. The test case containing n=0 will terminate the input, you should not give an answer to this case.

输出:

Output the number of pairs of candies that the cleverest little child can take home. Print your answer in a single line for each test case.

样例输入:

5
1 2 3 4
1 5 6 7
2 3 3 3
4 9 8 6
8 7 2 1
1
1 2 3 4
3
1 2 3 4
5 6 7 8
1 2 3 4
0

样例输出:

8
0
3

/*

http://acm.hdu.edu.cn/showproblem.php?pid=1514

题意是给4堆(堆的高度小于等于40)有颜色(颜色的种类小于等于20)的物品,你有一个篮子最多能装5件物品,每次从这4堆物品里面
任取一件物品放进篮子里,但是取每堆物品时,必须先取上面的物品,才能取下面的物品,如果发现篮子里
的两种物品的颜色一样,那么把这两种物品拿出来,问最后最多能拿出多少对物品?;

解题思路:记忆化搜索+dp+状态压缩;

因为40×40×40×40不会太大,所以可以用dp[x[1]][x[2]][x[3]][x[4]]记录搜索的状态;

dp[x[1]][x[2]][x[3]][x[4]]记录4堆分别从x[1],x[2],x[3],x[4]处往下取所获得的最大值;

因为颜色种类最多20种,可以对篮子里的物品颜色用每个位来存储,所以就用到了位状态压缩;

最后就是一步一步的试探搜索了;

*/

 

#include<stdio.h>
#include<string.h>
int num[45][5],n;
int x[5],dp[45][45][45][45];
int dfs(int market,int cnt)
{
 int sum,i,bit,Max=0;
 if(dp[x[1]][x[2]][x[3]][x[4]]!=-1)
  return dp[x[1]][x[2]][x[3]][x[4]];
 for(i=1;i<=4;i++)
 {
  sum=0;
  x[i]++;
  if(x[i]<=n){
   bit=(1<<num[x[i]][i]);
   if(market&bit)
    sum=dfs(market&(~bit),cnt-1)+1;
   else if(cnt<4)
    sum=dfs(market|bit,cnt+1); 
  }
  if(sum>Max)Max=sum;
  x[i]--;
 }
 dp[x[1]][x[2]][x[3]][x[4]]=Max;
 return Max;
}
int main()
{
 int i,j;
 while(scanf("%d",&n),n)
 {
  for(i=1;i<=n;i++)
   for(j=1;j<=4;j++)
    scanf("%d",&num[i][j]);
  x[1]=x[2]=x[3]=x[4]=0;
  memset(dp,-1,sizeof(dp));
  printf("%d\n",dfs(0,0));
 }
 return 0;
}

 

解题报告转自:http://blog.csdn.net/zkfzkfzkfzkfzkfzkfzk/article/details/7917389


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。