|
我来组成分块……
|
|
单调队列= =一开始加入写错了
设当前正在处理第K位，则向单调队列中加入f[i-l],并删除单调队列中在i-r之前的数字 好像只能分析K点从哪里来，不能用从哪个点可以到K 即只能用f[k]=Max{f[k-i]+cold[k]}i∈[l,r] 反正做对了~\(≧▽≦)/~ |
|
|
|
|
貌似裸判断的实际复杂度比O(mn)好的多得多……
|
|
区间贪心
|
|
|
为了艾尔
题目 1179 [郑州101中学] 圣战
2014-08-20 11:25:52
|
|
最简单的方法，预处理成01背包
|
|
|
BFS+dp
|
|
|
拓扑排序版
|
|
|
先用Floyd找到直径，由于这是一棵无根树，树中两点最短距离最大的就是直径的两个端点
或者从任意点v为根找到v点距离最大的点u 然后以u为直径的一个端点找距离u最大的点f为直径的另一个端点 然后就是枚举路径长度取最小值 |
|
|
|
开几个数组记录，O(n)扫描一下，注意对正在处理的区间的操作
|
|
|
线性匹配使用O(n)的算法
|
|
|
迭代实现+打表
|
|
单调队列搞定。。。代码55行，好像还是太长了
|
|
|
要么优先队列O(nlogn)过，要么计数排序然后直接用单调队列O(n)过，要么开O2暴力O(n^2)卡过，那些手写堆的大爷都是什么心态。。。
|
|
|
|
|
终于过了= =........................................先说下思路，二分答案然后最短路，关键就是最短路,我先是写的SPFA一直WA是因为排序的时候忘记记录以前的顺序了，然后有一个点T，因为SPFA更适合跑稀疏图，而倒数第二个点有1W个点，5W条边，然后开始想打dijk,一个点一直WA，最后发现原来是dijk写错了，这居然可以过9个点！！！不可思议......虽然花了很长时间但纠正了一些毛病....
|
|
|
原先（在2012-3-31添加的题目）这道题的数据是错误的（全是NIE），现在我改成了POI的官方数据，然后重评了所有提交O(∩_∩)O~~
|
|
|
线性规划模板题，数据淼求轻虐……
|