学步园

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3602

2010
ACM-ICPC Multi-University Training Contest（16）——Host by NUDT

题目大意：2012马上到了，X公司建造了m驾诺亚方舟，每个诺亚方舟最多装k个人，现在总共有n个国家的总统打算乘坐方舟，每个总统i有a[i]个贴身保镖来保护自己，这些保镖跟总统必须要同在一艘方舟上，需要支付b[i]的费用。因为国家有强又弱，总统信息按由强到弱给出，弱国的总统乘坐的方舟号不能小于强国的方舟号，X公司想获得最大的收益，求X公司的最大收益。

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXX=10005;
const int inf=1<<30;

int dp[MAXX]; //dp[i]表示获得收益i时方舟的位子占用情况
int a[101],b[101];

int cal(int a,int b,int k){//这地方就是处理加上b人后占用方舟的情况
	if(a%k==0)return a+b;//说明a人整好能占满x条方舟的所以增加的b人只需要新开以艘方舟就可以了
	int temp=a+b;
	if(temp%k==0)return temp;//说明如果a+b人整好能占满x艘方舟的话，直接返回占座情况a+b个座位
	if((a/k)<(temp/k))return (a/k+1)*k+b;//说明若a+b坐在一艘船上则b人不能坐在一块，所以要把那b个人单独放在一艘新的方舟上
	return temp;
}

int min(int a,int b){
	return a<b?a:b;
}

int main(){
	int t,n,m,k,i,j,limit;
	scanf("%d",&t);
	while(t--){
		limit=0;
		scanf("%d%d%d",&n,&m,&k);
        for(i=0;i<n;i++){
			scanf("%d%d",&a[i],&b[i]);
			a[i]++;
			limit+=b[i];
		}
		for(i=0;i<=limit;i++){
			dp[i]=inf;
		}
		dp[0]=0;
        for(i=0;i<n;i++){
			for(j=limit-b[i];j>=0;j--){
				if(a[i]<=k && dp[j]!=inf){
					dp[j+b[i]]=min(dp[j+b[i]],cal(dp[j],a[i],k));
				}
			}
		}
		for(i=limit;i>=0;i--){
			if(dp[i]<=m*k){
				break;
			}
		}
		printf("%d\n",i);
	}
	return 0;
}