sicily 1346 金明的预算方案 有依赖的背包问题

他还从因特网上查到了每件物品的价格（都是10元的整数倍）

注意这句话就ok了。。之间没留意，结果TLE

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
struct node {
	int v;			//价格
	int p;			//重要度
	int q;			//所属主件的编号
}data[61];
int f[60][32001];            //物品组
int n, m;
int ans[32001];
int main() {
	//freopen("1.txt", "r", stdin);
	while(cin >> n >> m) {
		memset(f, -1, sizeof(f));
		f[0][0] = 0;
		n /= 10;
		for(int i = 1; i <= m; i++) {
			cin >> data[i].v >> data[i].p >> data[i].q;
			data[i].v /= 10;
			f[i][0] = 0;
		}
		//对附件集合进行一次01背包
		for(int i = 1; i <= m; i++) {
			if(data[i].q == 0) continue;
			for(int j = n; j >= data[i].v; j--) {
				if(f[data[i].q][j - data[i].v] != -1) {
					f[data[i].q][j] = max(f[data[i].q][j], f[data[i].q][j - data[i].v] + data[i].v * data[i].p);
				}
			}
		}
		//对价值进行处理，更新为各物品组主件+附件
		for(int i = 1; i <= m; i++) {
			if(data[i].q != 0) continue;
			for(int j = n; j >= 0; j--) {
				if(f[i][j] != -1) {
					if(j + data[i].v > n) f[i][j] = -1;
					else {
						f[i][j + data[i].v] = max(f[i][j + data[i].v], f[i][j] + data[i].v * data[i].p);
						f[i][j] = -1;
					}
				}
			}
		}
		//变成有物品组的背包问题
		memset(ans, -1, sizeof(ans));
		ans[0] = 0;
		int _max = 0;
		for(int i = 1; i <= m; i++) {
			if(data[i].q != 0) continue;
			for(int j = n; j >= data[i].v; j--) {
				for(int k = j; k >= data[i].v; k--) {
					if(f[i][k] != -1 && ans[j - k] != -1) {
						ans[j] = max(ans[j], f[i][k] + ans[j - k]);
						_max = max(_max, ans[j]);
					}
				}
			}
		}
		cout << _max * 10 << endl;
	}
 	return 0;
}