UVA-10118-Free Candies

心已赠人 2021-12-23 11:34 79阅读 0赞

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

### 题意： ###

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

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

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

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

### 思路： ###

记忆化搜索。dp。

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

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

### 代码： ###

#include <iostream>
    #include <memory.h>
    #include <vector>
    #include <map>
    #include <algorithm>
    #include <cstdio>
    #include <math.h>
    #include <queue>
    #include <string>
    #include <stack>
    #include <iterator>
    #include <stdlib.h>
    #include <time.h>
    #include <assert.h>
    
    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;
    }
    /*
    3
    1 2 3 4
    5 6 7 8
    1 2 3 4
     */

转载于:https://www.cnblogs.com/YDDDD/p/10665449.html