建造堤坝

题目描述

在一个大型水利建设项目中，工程师们正在努力完成最后一段堤坝的建造。这段堤坝的完成需要至少体积为

v

的混凝土。目前，工地上有

n

批次不同规格的混凝土，每批次的体积和运输到堤坝现场所需的成本分别为

k

和

m

。由于工程已经进行了很长时间，预算有限，剩余的预算为

c

。

输入格式

第一行是三个整数：

v,n,c

。

从第二行到第

n+1

行分别为每批次混凝土的体积和运输到堤坝现场所需的成本。

输出格式

输出只有一行，如果工程师们能够完成堤坝的建造，则输出他们完成建造后剩下的最大预算，否则输出 Impossible （不带引号）。

样例 #1

样例输入 #1

CPP

100 2 10
50 5
50 5

样例输出 #1

CPP

样例 #2

样例输入 #2

CPP

10 2 1
50 5
10 2

样例输出 #2

CPP

Impossible

提示

数据范围及约定

对于 $20\%$ 的数据， $0<n \le 50$ ；
对于 $50\%$ 的数据， $0<n \le 1000$ ；
对于 $100\%$ 的数据， $0<n \le 10^4$ ，所有读入的数均属于 $[0,10^4]$ ，最后答案不大于 $c$ 。

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int v2,n,c,sum,mmin=10000000001;//c=背包容量 
int w[1000001],v[1000001];
int f[1000001];
bool isok=false;
int main(){
	cin>>v2>>n>>c;
	for(int i=1;i<=n;i++) {
		cin>>w[i]>>v[i];
		sum+=w[i];
		mmin=min(mmin,v[i]);
	}
	if(mmin>c || sum<v2) {
		cout<<"Impossible";
		isok=true;
	}
	for(int i=1;i<=n;i++){
		for(int j=v2;j>=w[i];j--){
			if(f[j-1]==0) f[j]=f[i-w[i]]+v[i];
			f[j]=max(f[i-1],f[i-w[i]]+v[i]);
		}
	}
	//if(sum<v2 || (c-f[v2])<0) cout<<"Impossible"<<endl;
	if(isok==true) return 0;
	else cout<<f[c];
	return 0;
}

求助站外题(WA10pts)

讨论操作