dp - HNU 13404 The Imp
2024-10-19 06:27:49
The Imp
Problem's Link: http://acm.hnu.cn/online/?action=problem&type=show&id=13404&courseid=0
Mean:
n个物品,每个物品价值为v,价格为c,你只可以带一个物品离开。
有一个精灵,它可以施法让你购买后的物品价值变为0(未离开商店之前),精灵最多施k次法术。
你的目的是让自己获得最大收益,而小鬼的目的正好相反。
如果你和精灵都采用最优策略,最后你可以盈利多少?
analyse:
第一感觉是三维dp,然而三维肯定会超时超内存。
然后就是想怎样压缩状态。。。
想了想其实两维就够了,为什么呢?因为对于第i件物品,如果我不选,那么它这次施不施法是没有影响的。
dp[i][j]:判断到第i个物品,精灵施了j次魔法,我还能获得的最大收益。
状态转移方程:dp[i][j]=max(dp[i-1][j],min(dp[i-1][j-1]-c,v-c))
伪代码:
for_each i
{
if(select i)
{
for_each j
{
if(magic j time)
{
max(before i) - cost;
}
else
{
value-cost;
}
}
}
else
{
max(before i);
}
}
{
if(select i)
{
for_each j
{
if(magic j time)
{
max(before i) - cost;
}
else
{
value-cost;
}
}
}
else
{
max(before i);
}
}
Time complexity: O(N*K)
Source code:
;
);
; );
; ; ;
}
/*
);
; );
; ; ;
}
/*
*/
最新文章
- Python Django 数据库操作
- Testing - 测试基础 - 用例
- C# 添加excel批注
- Python基础:映射(字典)
- windows系统命令服务安装卸载
- Python基础:1.数据类型(空、布尔类型、整型、长整型、浮点型、字符串)
- java.lang.String类compareTo()返回值解析
- java文件上传--基于ajaxFileUpload+struts2
- libtiff库使用
- python爬虫项目(scrapy-redis分布式爬取房天下租房信息)
- Flask插件wtforms、Flask文件上传和Echarts柱状图
- MySqlHelper的封装
- es2015箭头函数的this
- jar包的读取
- editable : false与 readonly 的区别
- python 之 string() 模块
- Android 之 SharedPreferences应用
- /var/log/messages Logging not working on Centos 7
- git一键提交修改文件
- java 实验5 图形用户界面设计试验
热门文章
- 创建组件“AxLicenseControl”失败
- [每日一题] OCP1z0-047 :2013-08-25 正则表达式REGEXP_LIKE-----‘harddisks’.................108
- vue - 减少打包后的体积
- 首都医科大学附属北京安贞医院全院级PACS系统采购项目[转]
- UNIX网络编程读书笔记:原始套接口
- HTML5 本地存储形式
- alitomcat maven以及Autoconfig
- window 10下 MySql5.7压缩包安装
- Tomcat中配置MySQL数据库连接池
- jquery api 常见api 效果操作例子