现在的位置: 首页 > 综合 > 正文

hdu2191

2014年01月21日 ⁄ 综合 ⁄ 共 624字 ⁄ 字号 评论关闭
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#define INF 99999999
using namespace std;

const int MAX=101;
int dp[MAX];//花费i元能购买的大米的最大重量 
int s[MAX][3];

int main(){
	int n,m,k,t;
	cin>>t;
	while(t--){
		cin>>n>>m;
		memset(dp,0,sizeof dp);
		for(int i=0;i<m;++i)cin>>s[i][0]>>s[i][1]>>s[i][2];
		for(int i=0;i<m;++i){
			for(k=1;k*2-1<=s[i][2];k=k*2){
				for(int j=n;j>=s[i][0]*k;--j){
					dp[j]=max(dp[j],dp[j-s[i][0]*k]+s[i][1]*k);
				}
			}
			for(int j=n;j>=(s[i][2]-k+1)*s[i][0];--j){
				dp[j]=max(dp[j],dp[j-(s[i][2]-k+1)*s[i][0]]+(s[i][2]-k+1)*s[i][1]);
			}
		}
		cout<<dp[n]<<endl;
	}
	return 0;
}

抱歉!评论已关闭.