1/36
文档分类:IT计算机

ACM课件(lecture 13).ppt


下载后只包含 1 个 PPT 格式的文档,里面的视频和音频不保证可以播放,查看文件列表

特别说明:文档预览什么样,下载就是什么样。

下载所得到的文件列表
ACM课件(lecture 13).ppt
文档介绍:
ACM课件(lecture_13)ACM程序设计
1
2021/7/21
今天,
你开始 了吗?
复****2
2021/7/21
本周双星(12):
06092602黄晓黎
mondayblue
3
2021/7/21
第十三讲
动态规划(2)
(Dynamic Programming)
4
2021/7/21
例1: HDOJ_1421 搬寝室
Sample Input
2 1 1 3
Sample Output
4
5
2021/7/21
第一感觉:
根据题目的要求,每次提的两个物品重量差越小越好,是不是每次提的物品一定是重量相邻的物品呢?
证明:假设四个从小到大的数:a、b、c、d,只需证明以下表达式成立即可:
(a-b)^2+(c-d)^2< (a-c)^2+(b-d)^2
(a-b)^2+(c-d)^2< (a-d)^2+(b-c)^2
……(略)
6
2021/7/21
预备工作:
排序!
7
2021/7/21
第二感觉:
对于一次操作,显然提的物品重量越接近越好,是不是可以贪心呢?
请思考…
考虑以下情况:
1 4 5 8
什么结论?
8
2021/7/21
详细分析:
从最简单的情况考虑:
2个物品选一对,结论显然
结论?
4个物品选一对?(如何利用前面的知识)
3个物品选一对,…
n个物品选一对,…
最终问题:n个物品选k对,如何?(n>=2k)
n个物品选二对,…
9
2021/7/21
本题算法(略):
哪位同学做个陈述?
10
2021/7/21
内容来自淘豆网www.taodocs.com转载请标明出处.
非法内容举报中心
文档信息
  • 页数36
  • 收藏数0 收藏
  • 顶次数0
  • 上传人liangwei2201
  • 文件大小228 KB
  • 时间2021-07-21