【洛谷】P1510 精卫填海
洛谷
2023-09-14 09:13:20 时间
1.题意
略
2.分析
裸的 0/1背包
3.代码
1.数组定义
dp[i]
表示到达体积i时需耗费的最小体力need
表示东海填平需要的木石体积v[i],cos[i]
每块石头的体积以及消耗的体力n
:西山的木石rest
:精卫剩余的体力
2.坑点:
题目说至少需要体积为v(代码里对应为need)的木石才可以填平。也就是说,我们可以在 >=need
的结果集中选择一个最小的体力消耗的就OK了。
#include<iostream>
#include<algorithm>
using namespace std;
const int INF = 0x3f7f7f7f;
const int maxN = 20005;
const int step = 10000;//即使多一块也无妨,多出来的一部分最长是step
int need,n,rest;
int dp[maxN],v[maxN],cost[maxN];
int main(){
cin >> need >> n >> rest;
for(int i = 0;i< n;i++){
cin >> v[i] >> cost[i];
}
fill(dp,dp+maxN,INF);
dp[0] = 0;
for(int i = 0;i< n;i++){
for(int j = need+step ; j >= v[i];j--){
if(dp[j-v[i]]!=INF){//如果dp[j-v[i]]可达
dp[j] = min(dp[j],dp[j-v[i]]+cost[i]);
}
}
}
int res = INF;
for(int i = need;i<=need+step;i++){ //这里任何一个i都是满足条件的
if(dp[i]!=INF)
res = min(dp[i],res);
}
if(res > rest)
cout << "Impossible\n";
else
cout << rest - res<<"\n";
}
相关文章
- 洛谷P1331 海战 题解
- 洛谷 P3419 [POI2005]SAM-Toy Cars题解
- 洛谷 P1992 不想兜圈的老爷爷 题解
- 洛谷-最长公共子串「建议收藏」
- 洛谷P1996 约瑟夫问题 c++链表做法
- 如何在洛谷写博客
- 【day1】【洛谷算法题】-B2002Hello,World-刷题反思集[入门1顺序结构]
- 【题解】洛谷P1003铺地毯
- 洛谷CF1744A题解
- 洛谷P1048
- 洛谷P1143
- 【洛谷-图论】P1807 最长路
- 【洛谷-拓扑排序】P4017 最大食物链计数
- 【洛谷习题】P5318 【深基18.例3】查找文献
- 【洛谷习题】P1255 数楼梯
- 【括号匹配&洛谷&进制转换】栈的实战,包教包会
- 洛谷CF1759B题解
- 洛谷-3月月赛2-Div.2