UVALive 4987 EvacuationPlan（dp，贪心）
2024-09-07 14:37:31
在所有避难所都有至少一只队伍的情况，总移动距离最小。
把队伍的位置和人都排序。
会发现，对于最后一个队伍i和最后一个避难所j，
Case 1：pos[j]>=pos[i]，那么i是距离j最近的一只队伍，
Case 2：pos[j]<pos[i]，那么j是距离i最近的一个避难所。
dp[i][j]表示第i个人，第j个避难所非空的最小总距离。
转移：对于第i个人，只需要往j走就好了。
Case 1,如果i走到最近的避难所j'，那么必须要有i之前的某个i'走到j，不会更优。
Case 2,直接贪心。
j已经有队伍了，前i-1个人可以进j也可以不进。
dp[i][j] = min(dp[i-1][j],dp[i-1][j-1])+dist(i,j).
可以从大到小枚举j把空间优化成一维。
路径用过bitset和bool。结果bitset慢了200ms...
想了很久的贪心的只能水过样例。还是n^2的dp稳啊。
最新文章
- ASP.NET MVC Model验证(一)
- ubuntu更新软件源
- pod导入融云路径报错解决办法
- 【BZOJ】1018: [SHOI2008]堵塞的交通traffic
- Chart控件，把Y轴设置成百分比
- CI框架 数据库批量插入 insert_batch()
- [ActionScript 3.0] AS3.0 生成xml方法之一
- [大牛翻译系列]Hadoop（13）MapReduce 性能调优：优化洗牌（shuffle）和排序阶段
- bq27441-G1 工作机制
- EMS-keil C51常用错误
- UMl概述（转）
- hdu_5961_传递（bitset）
- android脚步---不同activity之间参数传递
- 使用puppet
- 十四、使用framebuffer填充纯色
- Git使用详细教程(6)：git mv重命名文件
- python中和生成器协程相关的yield之最详最强解释，一看就懂（一）
- 为什么要用Thrift
- Reveal：分析iOS UI的利器
- C#调用XmlSerializer序列化时生成CDATA节点解决方法