https://vjudge.net/problem/UVA-10118

题目

桌上有4堆糖果，每堆有$N$（$N\leqslant 40$）颗。有个熊孩子拿了个可以装5颗糖的篮子，开始玩无聊的装糖游戏。他每次选一堆糖，并把这堆最上面的糖装进篮子里面，如果篮子里有两个种类相同的糖，那么他就把这两个糖装进自己的口袋里。给出四堆糖中每一颗糖的种类（1..20），问最多能装多少对糖。

题解

一开始看这题，拿糖的顺序有$\mathcal{O}(P(4^40,40))$种，一下就茫然了（估计得太松了……）

设dp[a][b][c][d]为分别拿了这么多桌上的糖的数量时最多还能拿多少糖，很容易写出转移方程……

这样状态数为$\mathcal{O}(n^4)$，转移数为4，复杂度$\mathcal{O}(n^4)$，还是可以

有个问题是篮子的空间有限制，但四堆糖确定后篮子剩余空间就确定了

计算到这里的时候说明能到达这个状态

因为一旦篮子里有两个相同的糖就会装进口袋，所以篮子里不会有两个相同的糖

那么要到达这个状态，篮子里一定只剩拿了奇数的糖

（又是乱证明= =）

只有20种糖，直接二进制压位

AC代码

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cctype>

using namespace std;

#define REP(r,x,y) for(register int r=(x); r<(y); r++)

#define PER(r,x,y) for(register int r=(x); r>(y); r--)

#define REPE(r,x,y) for(register int r=(x); r<=(y); r++)

#define PERE(r,x,y) for(register int r=(x); r>=(y); r--)

#ifdef sahdsg

#define DBG(...) printf(__VA_ARGS__)

#else

#define DBG(...) (void)0

#endif

int d[47][47][47][47];

int p[47][4];

int n;

int DP(int arr[4], int k, int cp) {

	int &now=d[arr[0]][arr[1]][arr[2]][arr[3]];

	if(now>=0) return now;

	now=0;

	REP(i,0,4) {

		if(arr[i]<n) {

			int iid=p[arr[i]][i];

			arr[i]++;

			if(k&(1<<iid)) {

				now = max(now,DP(arr,k^(1<<iid),cp-1)+1);

			} else {

				if(cp+1<=4) {

					now = max(now,DP(arr,k^(1<<iid),cp+1));

				}

			}

			arr[i]--;

		}

	}

	return now;

}

int main() {

#ifdef sahdsg

	freopen("in.txt", "r", stdin);

#endif

	while(~scanf("%d", &n) && n) {

		memset(d,-1,sizeof d);

		REP(i,0,n) {

			scanf("%d%d%d%d", &p[i][0], &p[i][1], &p[i][2], &p[i][3]);

		}

		int h[4]; memset(h,0,sizeof h);

		DP(h,0,0);

		printf("%d\n", d[0][0][0][0]);

	}

	return 0;

}

巴特西

UVA 10118 Free Candies

题目

题解

最新文章

热门文章