书海扬帆的博客

题目传送门

解题思路

转化为一般的01背包进行求解,最后枚举体力,当目前填的体积>=应该填的体积时,输出最大的体力值。

代码分享

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;
const int maxn=1001000;
int V,N,C;
int dp[maxn],d[maxn],v[maxn];
//d 价值 v体积
int main() {
scanf("%d%d%d",&V,&N,&C);
for(int i=1;i<=N;i++) {
scanf("%d%d",&v[i],&d[i]);
}
for(int i=1;i<=N;i++) {
for(int j=C;j>=d[i];j--) {
dp[j]=max(dp[j],dp[j-d[i]]+v[i]);
}
}
for(int i=1;i<=C;i++) {
if(dp[i]>=V) {
printf("%d\n",C-i);
return 0;
}
}
printf("Impossible");
return 0;
}


本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:730.1k