UVA - 10118 Free Candies(免费糖果)(dp---记忆化搜索)

时间：2023-01-25 08:05:49

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

分析：

1、dp[a][b][c][d]表示，当4堆糖果分别剩下a，b，c，d颗时，能拿到的最大糖果对数。

2、糖果种类最多20，所以用vis数组标记篮子里是否有该糖果。

#pragma comment(linker, "/STACK:102400000, 102400000")

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<cmath>

#include<iostream>

#include<sstream>

#include<iterator>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<deque>

#include<queue>

#include<list>

#define Min(a, b) ((a < b) ? a : b)

#define Max(a, b) ((a < b) ? b : a)

const double eps = 1e-8;

inline int dcmp(double a, double b){

    if(fabs(a - b) < eps) return 0;

    return a > b ? 1 : -1;

}

typedef long long LL;

typedef unsigned long long ULL;

const int INT_INF = 0x3f3f3f3f;

const int INT_M_INF = 0x7f7f7f7f;

const LL LL_INF = 0x3f3f3f3f3f3f3f3f;

const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;

const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};

const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};

const int MOD = 1e9 + 7;

const double pi = acos(-1.0);

const int MAXN = 40 + 10;

const int MAXT = 10000 + 10;

using namespace std;

int dp[MAXN][MAXN][MAXN][MAXN];

int v[5][MAXN];

int top[5];//堆顶下标

int N;

bool vis[25];

void init(){

    memset(dp, -1, sizeof dp);

    memset(v, 0, sizeof v);

    memset(top, 0, sizeof top);

    memset(vis, false, sizeof vis);

}

int dfs(int num){//num表示篮子里的糖果数

    if(dp[top[0]][top[1]][top[2]][top[3]] != -1) return dp[top[0]][top[1]][top[2]][top[3]];

    if(num == 5) return dp[top[0]][top[1]][top[2]][top[3]] = 0;//篮子里此时有5颗糖果，当前状态，不能拿到成对的糖果。

    int ans = 0;

    for(int i = 0; i < 4; ++i){

        if(top[i] == N) continue;//第i堆糖果已拿完

        int color = v[i][top[i]];

        vis[color] = !vis[color];//篮子里要么没有该糖果，要么只有一个该糖果，分别用false，true表示

        ++top[i];//拿走糖果，堆顶下标下移

        if(vis[color]){//之前没有该糖果，将糖果放进篮子，篮子糖果数加1

            ans = Max(ans, dfs(num + 1));

        }

        else{//之前已有该糖果，将糖果放进篮子，可取出一对糖果，篮子糖果数减1

            ans = Max(ans, dfs(num - 1) + 1);

        }

        vis[color] = !vis[color];

        --top[i];

    }

    return dp[top[0]][top[1]][top[2]][top[3]] = ans;

}

int main(){

    while(scanf("%d", &N) == 1){

        if(!N) return 0;

        init();

        for(int i = 0; i < N; ++i){

            for(int j = 0; j < 4; ++j){

                scanf("%d", &v[j][i]);

            }

        }

        printf("%d\n", dfs(0));

    }

    return 0;

}

相关文章