UVA10118（记忆化搜索 + 好题）

http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=19440

题意，4堆不同颜色的糖果，每堆N个，从堆上往下拿，放入一个最大装5个糖果的篮子里，如果糖果颜色相同就能将这两个放入自己口袋，问最多能放多少

分析：dp[1][2][3][4]表示取每一堆的第1，2，3，4个的情况，top[i]表示第i堆该取的个数，记忆化搜索

#include <iostream>

#include <cstring>

#include <algorithm>

#include <cstdio>

using namespace std;

const int MAX = ;

int dp[MAX][MAX][MAX][MAX],has_color[MAX],pile[][MAX],top[];

int n;

int dfs(int cnt)

{

    if(dp[ top[] ][ top[] ][ top[] ][ top[] ] != -)

        return dp[ top[] ][ top[] ][ top[] ][ top[] ];

    if(cnt == )  //如果已经取了5个，那就是0了

        return dp[ top[] ][ top[] ][ top[] ][ top[] ] = ;

    int ans = ;

    for(int i = ; i <= ; i++)

    {

        if(top[i] > n)

            continue;

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

        top[i] += ; //下一个

        if(has_color[color]) //有一个跟这个颜色相同

        {

            has_color[color] = ;

            ans = max(ans, dfs(cnt - ) + );//篮子里还能装cnt-1个，把篮子里那个拿出来

            has_color[color] = ;

        }

        else

        {

            has_color[color] = ;

            ans = max(ans, dfs(cnt + ));

            has_color[color] = ;

        }

        top[i] -= ;

    }

    return dp[ top[] ][ top[] ][ top[] ][ top[] ] = ans;

}

int main()

{

    while(scanf("%d", &n) != EOF && n)

    {

        for(int i = ; i <= n; i++)

        {

            for(int j = ; j <= ; j++)

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

        }

        memset(has_color, , sizeof(has_color));

        memset(dp, -, sizeof(dp));

        top[] = top[] = top[] = top[] = ;

        printf("%d\n", dfs() / );//至于这里为什么除以2，以为dfs时暴力了所有假设 是 1 ，2，2，3那么以第二堆为top[2】时能拿两个，以第三堆为top[3]时也能拿两个

    }

    return ;

}