度度熊与邪恶大魔王——dp
解析:本题使用dp,由于防御是0~10,所以可以求出每种防御对应各种血量所需要的最小晶石数目。用dp[j][i]表示消灭防御为i,血量为j的怪兽所需要的晶石数目。转移方程为:dp[j+v][i] = min(dp[j+v][i], dp[j][i]+k)。
发布日期:2021-06-29 05:37:52
浏览次数:2
分类:技术文章
本文共 2012 字,大约阅读时间需要 6 分钟。
度度熊与邪恶大魔王
Accepts: 2481
Submissions: 15467
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
具体见代码:
#include#include #include using namespace std;#define N 100005typedef long long ll;const ll INF=1e18+7;ll dp[1005][11];ll a[N], b[N], k[1005], p[1005];int main(){ int n, m; ll mxa, mxb, mxp; while(~scanf("%d%d", &n, &m)){ mxa = mxb = mxp = 0; for(int i = 0; i < n; i ++){ scanf("%I64d%I64d", &a[i], &b[i]); mxa = max(mxa, a[i]); mxb = max(b[i], mxb); } for(int i = 0; i < m; i++){ scanf("%I64d%I64d", &k[i], &p[i]); mxp = max(mxp, p[i]); } if(mxb >= mxp){ puts("-1"); continue; } for(int i = 0; i <= 10; i++){ for(int j = 0; j <= mxa; j++) dp[j][i] = INF; } for(int i = 0; i <= 10; i++){//防御 dp[0][i] = 0; for(int v = 0; v < mxa; v++){ for(int j = 0; j < m; j++){ if(p[j] <= i)continue; ll z = p[j] - i; if(v+z <= mxa) dp[v+z][i]=min(dp[v][i]+k[j],dp[v+z][i]); else dp[mxa][i]=min(dp[v][i]+k[j],dp[mxa][i]); } } } ll ans = 0; for(int i = 0; i <= 10; i++){ for(int j = mxa-1; j>0; j--){ for(int v = j; v <= mxa; v++) dp[j][i] = min(dp[v][i], dp[j][i]); } } for(int i = 0; i < n; i++) ans += dp[a[i]][b[i]]; printf("%I64d\n", ans); } return 0;}
转载地址:https://blog.csdn.net/zhj_fly/article/details/76749533 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年04月24日 09时25分30秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
什么是MySQL数据库?看这一篇干货文章就够了!
2019-04-29
刚看完zookeeper源码,各位随便问!
2019-04-29
给大家讲个笑话:公司空降了一名 “项目管理专家”
2019-04-29
漫画:什么是 “黑天鹅事件” ?
2019-04-29
家里有几十套房子,还当什么程序员?
2019-04-29
大数据薪资高,被这些岗位骗了!
2019-04-29
怎样的架构设计能力,才能成功拿下阿里P7(内含福利)
2019-04-29
漫画:如何螺旋遍历二维数组?(修订版)
2019-04-29
秋天的第一杯奶茶,我请了!
2019-04-29
漫画:什么是 “灰犀牛事件” ?
2019-04-29
手写Netty,超燃!
2019-04-29
什么是MySQL的执行计划(Explain关键字)?
2019-04-29
删库跑路升级版,著名大厂员工离职为报复公司,直接删虚拟机!
2019-04-29
“百度大脑” 放大招了!
2019-04-29
阿里p6的大数据开发工程师都要学什么?
2019-04-29
拿到这份“小抄”,字节面试妥了
2019-04-29
漫画:寻找股票买入卖出的最佳时机(动态规划)
2019-04-29
再见,斗鱼!再见,虎牙!
2019-04-29
蚂蚁金服的暴富还未开始,Zoom的神话却仍在继续!
2019-04-29