Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴个代码~~~

Posted by hzoi_hexing at 2014-01-17 20:27:55 on Problem 1276
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 1001000
#define M 1010
int f[N];
int w[M],c[M];
int n,m;

void mutipack(int w,int c,int amount){
	if (amount * c >= m){
		for (int i = c; i<=m; i++){
			f[i] = max(f[i - c] + w,f[i]);
		}
		return;
	}
	int k = 1;
	while (k <= amount){
		for (int i = m; i>= k*c; i--){
			f[i] = max(f[i],f[i - k*c] + k*w);
		}
		amount -= k;
		k <<= 1;
	}
	for (int i = m; i>=amount * c; i--){
		f[i] = max(f[i],f[i-amount*c] + amount*w);
	}
	return;
}

int main(){
	while (scanf("%d",&m) != EOF){
		scanf("%d",&n);
		for (int i = 1; i<=n; i++){
			scanf("%d%d",&c[i],&w[i]);
		}	
		memset(f,0,sizeof(f));
		f[0] = 0;
		for (int i = 1; i<=n; i++){
			mutipack(w[i],w[i],c[i]);
		}
		printf("%d\n",f[m]);
	}
	return 0;	
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator