2014-06-16

UVa 10118 - Free Candies

1. The Problem
2. The Input
3. The Output
4. Sample Input
5. Sample Output
6. Solution

The Problem

Little Bob is playing a game. He wants to win some candies in it - as many as possible.

There are 4 piles, each pile contains N candies. Bob is given a basket which can hold at most 5 candies. Each time, he puts a candy at the top of one pile into the basket, and if there’re two candies of the same color in it ,he can take both of them outside the basket and put them into his own pocket. When the basket is full and there are no two candies of the same color, the game ends. If the game is played perfectly, the game will end with no candies left in the piles.

For example, Bob may play this game like this (N=5):

Step1 Initial Piles Step2 Take one from pile #2
Piles Basket Pocket Piles Basket Pocket

1 2 3 4
1 5 6 7
2 3 3 3
4 9 8 6
8 7 2 1

nothing     nothing

1 3 4
1 5 6 7
2 3 3 3
4 9 8 6
8 7 2 1

2     nothing

Step3 Take one from pile #2 Step4 Take one from pile #3
Piles Basket Pocket Piles Basket Pocket

1 3 4
1 6 7
2 3 3 3
4 9 8 6
8 7 2 1

2 5     nothing

1 4
1 6 7
2 3 3 3
4 9 8 6
8 7 2 1

2 3 5     nothing

Step5 Take one from pile #2 Step6 put two candies into his pocket
Piles Basket Pocket Piles Basket Pocket

1 4
1 6 7
2 3 3
4 9 8 6
8 7 2 1

2 3 3 5     nothing

1 4
1 6 7
2 3 3
4 9 8 6
8 7 2 1

2 5     a pair of 3

Note that different numbers indicate different colors, there are 20 kinds of colors numbered 1..20.

‘Seems so hard…’Bob got very much puzzled. How many pairs of candies could he take home at most?

The Input

The input will contain no more than 10 test cases. Each test case begins with a line containing a single integer n(1<=n<=40) representing the height of the piles. In the following n lines, each line contains four integers xi1,xi2,xi3,xi4 (in the range 1..20). Each integer indicates the color of the corresponding candy. The test case containing n=0 will terminate the input, you should not give an answer to this case.

The Output

Output the number of pairs of candies that the cleverest little child can take home. Print your answer in a single line for each test case.

Sample Input

Sample Output

1
2
3

8
0
3

Solution

題目描述：

現在盤面上共有 4 堆，每一堆呈現 stack 的方式，並且每一堆都會有 n 個糖果，接下來每一步將會把每一堆的 top 糖果放入籃子中，假使籃子中有相同編號的糖果，則會將這兩個相同編號的糖果收入口袋。請問到籃子滿 5 個糖果之前，最多有多少對的糖果可以帶回家。

題目解法：

將搜索狀態進行標記，之後走訪遇到相同狀態直接退回。這個問題在相同狀態下的結果必然相同。

#include <stdio.h> 
#include <algorithm>
#include <iostream>
using namespace std;
#define MAXN 45
int N, pile[4][MAXN];
int used[MAXN][MAXN][MAXN][MAXN] = {}, testcase = 0;
int dp[MAXN][MAXN][MAXN][MAXN];
int dfs(int p1, int p2, int p3, int p4, int state) {
    if(__builtin_popcount(state) == 5)
        return 0;
    if(used[p1][p2][p3][p4] == testcase)
        return dp[p1][p2][p3][p4];
    used[p1][p2][p3][p4] = testcase;
    int &ret = dp[p1][p2][p3][p4];
    int t, v;
    ret = 0;
    if(p1 < N) {
        t = pile[0][p1];
        v = (state>>t)&1;
        ret = max(ret, v + dfs(p1+1, p2, p3, p4, state^(1<<t)));
    }
    if(p2 < N) {
        t = pile[1][p2];
        v = (state>>t)&1;
        ret = max(ret, v + dfs(p1, p2+1, p3, p4, state^(1<<t)));
    }
    if(p3 < N) {
        t = pile[2][p3];
        v = (state>>t)&1;
        ret = max(ret, v + dfs(p1, p2, p3+1, p4, state^(1<<t)));
    }
    if(p4 < N) {
        t = pile[3][p4];
        v = (state>>t)&1;
        ret = max(ret, v + dfs(p1, p2, p3, p4+1, state^(1<<t)));
    }
    return ret;
}
int main() {
    while(scanf("%d", &N) == 1 && N) {
        for(int i = 0; i < N; i++)
            for(int j = 0; j < 4; j++)
                scanf("%d", &pile[j][i]);
        testcase++;
        int ret = dfs(0, 0, 0, 0, 0);
        printf("%d\n", ret);
    }
    return 0;
}

Morris' Blog