UVA-10118-Free Candies-白红宇

UVA-10118-Free Candies

阅读量：6173 次

发布时间：2019-06-21

本文共 1442 字，大约阅读时间需要 4 分钟。

链接：https://vjudge.net/problem/UVA-10118

题意：

给你四个柱子，每个柱子有n个不同颜色的糖果。

每次只能取柱子顶的一个糖果。

手上最多抓5个糖果。但是手上每有2个相同的的糖果的时候可以将这一对糖果放到口袋。

求最多能放几对糖果到口袋。

思路：

记忆化搜索。dp。

dp[a][b][c][d]记录第一个柱子取a个，第二个柱子取b个。。。。的能得到的最大的对数。

Vis记录手上糖果颜色拥有的情况

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   using namespace std;typedef long long LL;const int MAXN = 40 + 10;int n;int dp[MAXN][MAXN][MAXN][MAXN];int a[7][MAXN];bool Vis[25];int use[10];int Dfs(int step){ if (dp[use[1]][use[2]][use[3]][use[4]] != -1) //当某种情况存在过之后就直接记录返回 return dp[use[1]][use[2]][use[3]][use[4]]; int res = 0; if (step == 5) return res; for (int i = 1; i <= 4; i++) { int tmp = 0; ++use[i]; if (use[i] > n) { --use[i]; continue; } if (Vis[a[i][use[i]]]) { Vis[a[i][use[i]]] = false; tmp = Dfs(step - 1) + 1; Vis[a[i][use[i]]] = true; } else { Vis[a[i][use[i]]] = true; tmp = Dfs(step + 1); Vis[a[i][use[i]]] = false; } --use[i]; res = max(res, tmp); } return dp[use[1]][use[2]][use[3]][use[4]] = res;}int main(){ while (cin >> n && n) { memset(dp, -1, sizeof(dp)); memset(use, 0, sizeof(use)); memset(Vis, false, sizeof(Vis)); for (int i = 1;i <= n;i++) { for (int j = 1;j <= 4;j++) { cin >> a[j][i]; } } cout << Dfs(0) << endl; } return 0;}/*31 2 3 45 6 7 81 2 3 4 */