bzoj 2654 && bzoj 3675 总结
手动博客搬家: 本文发表于20180929 15:18:55, 原地址https://blog.csdn.net/suncongbo/article/details/82897992
最近做到了两道(我感觉)思路比较神的题,总结一下。
注:以下两道题我都没有用文中所述方法A过。
1. bzoj 2654
首先如果直接求MST,不能保证有恰好\(K\)条白边。
而贪心显然是错的。
可以这样想:如果题目里要求是恰好有\(0\)条白边,我们可以让所有白边的代价增加\(+\inf\). 如果要求白边最多,可以让白边代价增加\(-\inf\). 那既然这样的话,MST中白边的数量一定随着给白边增加的权值单调。因此可以二分,直到有\(K\)条白边即可。最后答案减去\(K\times 增加的权值\).
好神啊www %%%cls
这道题非常重要,希望自己永远也不要忘记这道题。
2. bzoj 3675
正解是斜率优化dp. 但这不是本文的重点。
如果只是斜率优化不搞点有意思的新东西也太无聊了吧!23333
从网上看到的神做法:
首先\(dp\)还是要的:假设\(dp[i]\)表示序列前\(i\)个数分割成若干段的最大得分,则枚举最外层的一次划分\(dp[i]=\max^{i}_{j=1} (s[i]-s[j])s[j]\), \(s[j]\)为权值的前缀和。但是这样无法保证最优解能分成\(K\)段。行吧那我们假设\(dp\)方程长成了这样: \(dp[i]=\max^{i}_{j=1} (s[i]-s[j])s[j]+C\), \(C\)为常数。显然\(C \rightarrow +\inf\)时\(dp\)会自然而然地分成\(n\)段,反之\(C\rightarrow -\inf\)时会分成1段。因此可以二分\(C\), 当分的段数达到\(K\)时,就是答案。最后减去\(C\times K\).
这样做应该是过不了的,但是至少能为我们提供一种思路。
如果在这个算法的基础上加上斜率优化应该就差不多能过了,时间复杂度\(O(n\log W)\), \(W\)为值域。这样\(K\)如果也是\(1e5\)应该也能过了。
(其实我是通过这题才看懂的上一题23333)
最新文章
- 使用太过简单jqprint源码也极其简洁易懂
- 开发时建议关闭chrome的缓存[Disable cache(while DevTools open)]
- 以最简单的登录为例,诠释JS面向对象的简单实例
- A simple json-rpc case for bitcoin blockchains
- maven错误解决:编码GBK的不可映射字符
- 《python学习手册》之一——程序运行
- 从汇编来看c语言之变量
- Pig Apache Hadoop
- C# struct 性能损失
- iOS UISearchDisplayController学习笔记
- Erlang常用代码段
- python学习day3------列表、元组、字符串操作
- Chapter_3_JAVA作业
- 单页应用 WebApp SPA 骨架 框架 路由 页面切换 转场
- python:代码复用与函数递归
- 100M双绞线接头的标准接法
- Netty实践二(心跳检测)
- 学以致用十-----centos7.2+python3.6+vim8.1+YouCompleteMe
- DRF框架QQ登录功能
- js 根据title从下级往上级查找
热门文章
- ExtJs4.1布局具体解释
- @ConfigurationProperties注解
- Codeforces Round #332 (Div. 2) B. Spongebob and Joke 模拟
- C# winform窗体在桌面右下角显示(任务栏上方)
- kafka备份机制——zk选举leader,leader在broker里负责备份
- 520D
- PCB .NET连接MySQL与Oracle DLL文分享件 MySql.Data,Oracle.ManagedDataAccess
- Blender插件初始化范例
- Promise-js异步加载解决方案
- GitHub上fork别人打代码后如何保持和原作者同步的更新