PKU 2642-The Brick Stops Here

問題概要

1000gの煉瓦がいくつかある．それぞれの銅の含有量と価格があたえられたとき，
m個の煉瓦を持ちいて，銅の含有量がcmin以上cmax以下の煉瓦を作る時の最安値を求めよ

解法

動的計画法．煉瓦はn個あるとして，銅の含有量をw[i]，価格をc[i]とし，
dp[x][y]をy個の煉瓦に対してx[g]の銅を含有量の合計の時の最安値とすることで，
k番目の品物に対して，
dp[i][j]=min(dp[i-w[k]][j]+c[k],dp[i][j])
が成り立つ．

実装(C++)

#include <algorithm>
#include <vector>
#include <iostream>
#include <cstring>
using namespace std;

typedef long long int lli;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define rep(i,s,x) for(int i=s;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
int N,M;
int weight[200],price[200];
int dp[20001][21];//i[g]のものをj個使って作るときの最安値
int main(){
	cin>>N;
	REP(i,N){
		cin>>weight[i]>>price[i];
	}
	memset(dp,0x3F,sizeof(dp));
	dp[0][0]=0;

	for(int k=0;k<N;k++){
		for(int i=20000;i>=0;i--){
			if(i-weight[k]<0)break;
			for(int j=0;j<20;j++){
				dp[i][j+1]=min(dp[i][j+1],dp[i-weight[k]][j]+price[k]);
			}
		}
	}
	int c;
	cin>>c;
	int m,cmin,cmax;
	REP(i,c){
		cin>>m>>cmin>>cmax;
		int ans=0x7FFFFFFF;
		for(int i=cmin*m;i<=cmax*m;i++){
			ans=min(ans,dp[i][m]);
		}
		if(ans>0x2F3F3F3F){
			cout<<"impossible"<<endl;
		}else{
			cout<<ans<<endl;
		}
	}
}