记录编号	49533	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	还是“金明的预算方案”	最终得分	100
用户昵称	feng	是否通过	通过
代码语言	C++	运行时间	1.676 s
提交时间	2012-11-08 14:16:50	内存使用	10.60 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
struct node {  
    int v;    
	int p;
    int q;        
}data[61];  
int f[60][32001];           
int n,m,s;  
int ans[32001];  
int main() {
	freopen("budgetb.in","r",stdin);
	freopen("budgetb.out","w",stdout);
    cin>>n>>m>>s;
        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;  
        }  
        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;  
}