UVA10118 免费糖果

题意

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

解析

可用记忆化搜索。

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

用一个数组(函数参数也行)存储当前第 ii 堆拿走的个数。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#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;
}

UVA10118 免费糖果
https://www.d0j1a1701.cc/p/c0900c71/
作者
d0j1a_1701
发布于
2020年10月26日
许可协议
CC-BY-SA