JZOJ 1040. 【GDOI2007】夏娜的菠萝包

状压玩疯了

(Code)

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

int f[16][1 << 16] , st[1 << 16] , t[16] , d[16] , up[16];
int n , m , ans , sum[22] , can[22] , e[22] , w[22];

int main()
{
	while (1)
	{
		scanf("%d" , &n);
		if (n == 0) break;
		for(register int i = 1; i <= n; i++) scanf("%d%d" , &t[i] , &d[i]) , up[i] = t[i] / d[i] + 1;
		scanf("%d" , &m);
		int num , x;
		for(register int i = 1; i <= m; i++)
		{
			scanf("%d%d" , &num , &e[i]);
			sum[i] = w[i] = st[i] = 0 , can[i] = 0x3f3f3f3f;
			for(register int j = 1; j <= num; j++)
			{
				scanf("%d" , &x);
				can[i] = min(can[i] , up[x]) , sum[i] += t[x] , w[i] += d[x];
				st[i] |= 1 << x - 1;
			}
		}
		memset(f , 0 , sizeof f);
		for(register int i = 1; i <= m; i++) f[1][st[i]] = max(f[1][st[i]] , sum[i] + e[i]);
		for(register int i = 1; i < n; i++)
			for(register int j = 0; j < 1 << n; j++)
				for(register int k = 1; k <= m; k++)
				if (can[k] > i && !(j & st[k]))
					f[i + 1][j | st[k]] = max(f[i + 1][j | st[k]] , f[i][j] + sum[k] + e[k] - w[k] * i);
		ans = 0;
		for(register int i = 1; i <= n; i++)
			for(register int j = 0; j < 1 << n; j++)
				ans = max(ans , f[i][j]);
		printf("%d
" , ans);
	}
}