UVa 10118 免费糖果（记忆化搜索+哈希）

题意：

桌上有4堆糖果，每堆有N颗。佳佳有一个最多可以装5颗糖的小篮子。他每次选择一堆糖果，把最顶上的一颗拿到篮子里。如果篮子里有两颗颜色相同的糖果，佳佳就把它们从篮子里拿出来放到自己的口袋里。如果篮子满了而里面又没有相同颜色的糖果，游戏结束。

思路：

怎么判断糖果是否颜色相同是本题的一个重点，看了别人的思路后明白了用哈希是很好的办法。

因为一共只有20颗种类的糖果，所以只需要一个20大小的数组来判断糖果是否出现过。

top[5]数组用来标记每堆糖果所拿的个数。

 1 #include<iostream> 
 2 #include<string>
 3 #include<cstring>
 4 #include<sstream>
 5 #include<algorithm>
 6 using namespace std;
 7 
 8 const int maxn = 45;
 9 
10 int n;
11 int c[4][maxn];
12 int d[maxn][maxn][maxn][maxn];
13 int top[5];
14 bool Hash[25];
15 
16 
17 int dp(int cur)
18 {
19     int& ans = d[top[0]][top[1]][top[2]][top[3]];
20     if (ans)  return ans;
21     if (cur == 5)  return 0;   //篮子满了
22     for (int i = 0; i < 4; i++)
23     {
24         if (top[i] == n)  continue;   //已经取完
25         int x = c[i][top[i]++];
26         if (Hash[x] == true)
27         {
28             Hash[x] = false;
29             ans = max(ans, dp(cur - 1) + 1);
30             Hash[x] = true;
31         }
32         else
33         {
34             Hash[x] = true;
35             ans = max(ans, dp(cur + 1));
36             Hash[x] = false;
37         }
38         top[i]--;
39     }
40     return ans;
41 }
42 
43 int main()
44 {
45     //freopen("D:\txt.txt", "r", stdin);
46     while (cin >> n && n)
47     {
48         memset(d, 0, sizeof(d));
49         memset(top, 0, sizeof(top));
50         memset(Hash, false, sizeof(Hash));
51         for (int i = 0; i < n;i++)
52         for (int j = 0; j < 4; j++)
53             cin >> c[j][i];
54         cout << dp(0) << endl;
55     }
56     return 0;
57 }