hdu 3721 Ahui Writes Word 多重背包

刚开始是用01背包做，TLE，百度，发现这是多重背包。

ps：二进制拆分要熟练一点！！

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

int f[10001];
int n, c;
int a[11][11];

int main() {
	//freopen("1.txt", "r", stdin);
	char s[12];
	int vi, ci;
	while(cin >> n >> c) {
		memset(f, 0, sizeof(f));
		memset(a, 0, sizeof(a));
		for(int i = 0; i < n; i++) {
			scanf("%s%d%d", s, &vi, &ci);
			a[vi][ci]++;
		}
		for(int i = 0; i < 11; i++) {
			for(int j = 0; j < 11; j++) {
				if(a[i][j] == 0) continue;
				int count = 1;
				int sum = 0;
				while(sum < a[i][j]) {
					for(int k = c; k >= j * count; k--) {
						f[k] = max(f[k], f[k - j * count] + i * count);
					}
					sum += count;
					if(a[i][j] - sum < count * 2)
						count = a[i][j] - sum;
					else
						count *= 2;
				}
			}
		}
		printf("%d/n", f[c]);
	}
 	return 0;
}