【题解】UVA10118 免费糖果

题意

4堆糖果，每堆 $n$ 颗，每次拿最顶上的，篮子里能装5颗糖果，拿到两颗一样的就可以拿走，求最多能拿走多少颗。

解析

可用记忆化搜索。

用一个bitset(或bool数组)存储当前拿走的糖果颜色，如果拿糖果时已经拿过同颜色的可以将bitset相应位清零。

用一个数组（函数参数也行）存储当前第 $i$ 堆拿走的个数。

返回时将当前状态（每堆拿了几个）记录下来，再次搜索时直接返回。

别忘了每次输入时清空数组。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <bitset>
using namespace std;
int n,arr[50][5],mem[50][50][50][50],top[5];
bitset<50> take;//bitset更省空间
int dfs(int num){
	if(mem[top[0]][top[1]][top[2]][top[3]]!=-1)	return mem[top[0]][top[1]][top[2]][top[3]];//如果当前情况记忆化搜过了，直接返回
	if(num==5)	return mem[top[0]][top[1]][top[2]][top[3]] = 0;//如果口袋里还剩五颗糖果，不可能再拿到糖果
	int res=0;
	for(int i=0;i<4;i++){
		if(top[i]==n)	continue;//如果这一堆全拿光了就没法拿了
		int c = arr[top[i]][i];//当前糖果颜色
		take[c] = !take[c];//拿走糖果
		top[i]++;
		if(take[c]){//之前没拿这个糖果
			res = max(res,dfs(num+1));//糖果放进口袋，计算结果
		}else{
			res = max(res,dfs(num-1)+1);//否则拿出一对糖果，结果+1
		}
		take[c] = !take[c];//回溯
		top[i]--;
	}
	return mem[top[0]][top[1]][top[2]][top[3]] = res;//返回最优解
}
int main(){
	while(cin >> n && n!=0){
		memset(arr,0,sizeof(arr));
		memset(mem,-1,sizeof(mem));
		memset(top,0,sizeof(top));
		take = 0;
		for(int i=0;i<n;i++){
			cin >> arr[i][0] >> arr[i][1] >> arr[i][2] >> arr[i][3];
		}
		cout << dfs(0) << endl;
	}
	return 0;
}