【USACO3.3.2】商店购物 状态压缩动态规划

节约空间我自然用了滚动数组…… 偷懒用指针来实现滚动了。

用二进制标志状态。 因为最多只买5种商品。

所以f[][][][][]   每一维空间表示每个商品购买的情况，

这里只说一下二维的情况  f[i][j] = f[a][b] + a[p]  

其中：  b[p]+a = i     c[p] + b = j

说白了，就是用几维空间， 第一维，就是第一个商品的购买数量。  第二维就是第二个商品购买数量……  

假如  一个状态  5 3 4 2 1 就是第一个商品买5个，第二个商品买3个，第三个商品买4个，第四个商品买2个，第五个商品买1个。  【所花的最少费用】

那么转移就很明显了…… 直接"套餐"来转移。  为了省事， 把  【只购买一个商品】（也就是输入数据中，最后那几组数据）也列为套餐。

状态压缩呢， 因为题目说了，每个商品最多买5个，所以 用3位二进制来表示一个状态。   最多15个二进制位（这也是很小的）。

优化：  因为5只是100 而不是111. 所以不需要太多的穷举~ 当然我为了省事，我还是一直穷举到111了。

其他嘛，看程序就行了。略有备注。

Executing...
   Test 1: TEST OK [0.003 secs, 3636 KB]
   Test 2: TEST OK [0.003 secs, 3636 KB]
   Test 3: TEST OK [0.003 secs, 3636 KB]
   Test 4: TEST OK [0.005 secs, 3636 KB]
   Test 5: TEST OK [0.008 secs, 3636 KB]
   Test 6: TEST OK [0.003 secs, 3636 KB]
   Test 7: TEST OK [0.003 secs, 3636 KB]
   Test 8: TEST OK [0.003 secs, 3636 KB]
   Test 9: TEST OK [0.005 secs, 3636 KB]
   Test 10: TEST OK [0.043 secs, 3636 KB]
   Test 11: TEST OK [0.057 secs, 3636 KB]
   Test 12: TEST OK [0.035 secs, 3636 KB]

All tests OK.      

/*
TASK:shopping
LANG:C++
*/
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int kinds, tot_kinds;
int f[2][33000]={0};
int *f0 = f[0], *f1= f[1];
int tn[110];
int tk[110][10], tc[110][10], valve[110];
int rel[1000],req[10];
const int ooo[] = {7, 56,448,3584,28672};

void init()
{
	memset(f, 65, sizeof(f));
	memset(rel, -1, sizeof(rel));
	scanf("%d", &kinds);
	for (int i = 0; i != kinds; ++ i)
	{
		scanf("%d", &tn[i]); //i的优惠方案 要购买的数量 
		for (int j = 0; j != tn[i]; ++ j)		scanf("%d%d", &tc[i][j], &tk[i][j]);//k个编号为c 
		scanf("%d", &valve[i]); //第i套优惠方案的价格 
	}
	
	scanf("%d", &tot_kinds); //需要购买的只有b个产品 
	int tail = 0;

	for (int i = 0; i != tot_kinds; ++ i)
	{
		int c, k, p;
		scanf("%d%d%d", &c, &k, &p); // 编号c 要k个，原价是p 
		req[tail] = k;
		rel[c] = tail++;
		tn[kinds + i] = 1;
		tk[kinds + i][0] = 1;
		tc[kinds + i][0] = c;
		valve[kinds + i] = p;
	}
}

void doit()
{	
	memset(f0, 65, sizeof(f)/2);
	int inf = f0[0], st = 0;
	f0[0] = 0;//什么都不用的情况下，价格显然为0
	for (int i = st; i != kinds + tot_kinds; ++ i)
	{
		for (int ci = 0;; ++ ci)
		{
			int tmp = 0;
			for (int j = 0; j != tn[i]; ++ j)
			{
				int now = rel[tc[i][j]];
				int buy = tk[i][j];
				if (buy * ci > req[now])	goto breakfor2; //有不需要的，退出
				tmp += (buy * ci) << (now * 3);
			}
			for (int j = 0; j != (1 << (tot_kinds * 3)); ++ j) //穷举每个状态，判断是否可以转移，可以转移就转移一下
			{
				if (f0[j] == inf)	continue; //如果这个j的状态本来就不存在，肯定不可以转移
				//cout<<"j = "<<j<<endl;
				for (int k = 0; k != tot_kinds; ++ k)// 超出需求，退出,继续下一个循环
					if ((tmp & ooo[k]) + (j & ooo[k]) > (req[k] << (k * 3)))	goto breakfor3; 
				f1[j + tmp] = min(f0[j] + valve[i] * ci, f1[j + tmp]);
				breakfor3:;
			}
		}
		breakfor2:;
		swap(f0, f1);
		memset(f1, 65, sizeof(f)/2);
	}
	int tmp = 0;
	for (int i = 0; i != tot_kinds; ++ i)	tmp += req[i] << (i * 3);
	printf("%d\n", f0[tmp]);
}

int main()
{
	freopen("shopping.in","r",stdin);
	freopen("shopping.out","w",stdout);
	init();
	doit();
	return 0;
}
/*

2
1 7 3 5
2 7 1 8 2 10
2
7 3 2
8 2 5

*/