基础贪心常用策略

把每一堆纸牌的个数（下文记作 \(a_i\)）减去平均数（负数别管他就行），然后：

for(int i=1;i<=n;i++)
      if(a[i]/*!=0*/) //‘!=0’可省略（非零即真）
            a[i+1]+=a[i],cnt++; //cnt记录移动次数

令 a[]=原数 ，每次删去 \(i\) 最大且 \(a_i\le a_{i+1}\) 的一位，即可得到最小值。

这题大概是爆力。一直往上找和 \(n\) 二进制一的个数相同的数，最坏情况下复杂度是 \(O(n\log n)\)（当然实际最坏复杂度会比这个更低）。

按区间右端点从小到大排序后 \(1…n\) 先后无脑不重叠挑选区间。证明：当决策第 \(i\) 个区间时，\(r_i\)（右端点）以前的都已处理过，那么 \(r_i\) 更小必定会给 \(r_i\) 以后的区间留下更多空间。

同样按上一题方法排序。从 \(1…n\) 扫描区间，若当前区间还未包含过，则增加此区间的右端点入集合。证明：当决策区间 \(i\) 时，前 \(i-1\) 个端点已经决策完成，若要使后面的区间受益更多，必定将右端点取入集合。

记性价比=价值/质量，则优先拿性价比高的，直到把背包装满。

这题叫不了贪心吧……就是个爆力，没什么好说的了，就是枚举有没有点可以支配当前点，把所有不能被任何点支配的点输出（~~另外输出格式可能还比主程序难一些~~）

这题是 \(O(n^3)\) 前缀和+dp 好吗！！！

先预处理求每一列的前缀和。

再分别循环 \(l,r\)。把 a[l][i],a[l+1][i],a[l+2][i],...,a[r-1][i],a[r][i] 看作是一个整体（前缀和 \(O(1)\) 求），用最大子段模板和去做dp。

Tags: ybt