UVa 10118 Free Candies

题目

◇题目传送门◆（由于UVa较慢，这里提供一个vjudge的链接）
◇题目传送门（vjudge）◆

题目大意

桌上有4堆糖果，每堆有$N(N\le40)$颗，每颗糖都有一个颜色，共有20种颜色。Bob有一个能装5个糖的篮子，他每次可以从任意一堆糖中取出最顶上的一颗，若篮子中有两个糖颜色相同，他就会将它们从篮子中取出放到自己的袋子里，若篮子装满了且里面没有相同颜色的糖，则停止取糖，Bob口袋中的糖就归他了。求他最多能得到多少对糖。

思路

这道题的状态转移似乎有点困难。。。

只有试试记忆化搜索了。

我们定义状态$f[i][j][k][l]$为第一堆糖取到了第$i$个，第二堆糖取到了第$j$个，第三堆糖取到了第$k$个，第四堆糖取到了第$l$个所能得的最多的糖的数量。

我们再定义一个布尔数组tt<script type="math/tex" id="MathJax-Element-193">t</script>以记录各种颜色的糖在篮子中是否出现，若值为1，则表示该颜色的糖出现了一次，否则表示没有出现。（据说可以采用状态压缩，这里留给读者思考）

注意：转移后回溯时应改回数组值。

细节还是见代码吧。

正解代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const int Maxn=40;
const int Maxc=20;int N;
int A[Maxn+5][4];
int top[4];
int f[Maxn+5][Maxn+5][Maxn+5][Maxn+5];inline void Init() {memset(f,-1,sizeof f);memset(top,0,sizeof top);
}int DFS(int cnt,bool *t) {
   //cnt是当前篮子中糖的个数，数组t是标记糖的出现次数int &res=f[top[0]][top[1]][top[2]][top[3]];//定义一个引用，方便操作if(res!=-1)return res;if(cnt==5)return res=0;//篮子满了，直接返回0int ret=0;for(int i=0;i<4;i++) {if(top[i]>=N)continue;//这堆糖已经被拿完了top[i]++;int col=A[top[i]][i];if(t[col]) {t[col]=false;int tmp=DFS(cnt-1,t);//这时已经凑成了一对，则篮子中减少一个糖，当前答案增加1ret=max(ret,tmp+1);t[col]=true;} else {t[col]=true;int tmp=DFS(cnt+1,t);//否则此时篮子中增加一个糖ret=max(ret,tmp);t[col]=false;}top[i]--;//注意回溯！}return res=ret;
}int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifwhile(scanf("%d",&N)!=EOF&&N) {Init();for(int i=1;i<=N;i++)for(int j=0;j<4;j++)scanf("%d",&A[i][j]);bool t[Maxc+5];memset(t,0,sizeof t);printf("%d\n",DFS(0,t));}return 0;
}