T1:
给定两个数组 \(a,b\),要求将 \(b\) 重排,使得 \(b>a\) 的位置个数最多,在此基础上最大化 \(b\) 的字典序。
\(n\le 5000\)。
最多的位置个数是容易求的,排个序即可。
如何最大化字典序?依次枚举 \(i=1\sim n\),然后从大到小枚举 \(j\) 看看 \(b_i=j\) 是否可以让后面依然保持大于位置足够。
把 \(j>a_i\) 和 \(j\le a_i\) 两类分类,因为这会影响后面需要多少个大于位置。
明显的结论:一定是 \(a_{i+1\sim n}\) 的前 \(mx-now\) 小匹配。
进而,我们发现当 \(j-1\),只会影响 \(a\) 一个位置的对应方式。\(O(n^2)\)。
T2:
给定平面上 \(n\) 个点。求点的排列,使得前 \(i\) 个点与原点的外包矩形周长 的增加量最小。\(n\le 10^5\)。
断言:每次一定选使得增加量最小的哪个点。
证明:设这个点是 \(mn\),如果选了点 \(p\) 替代 \(mn\),不如把 \(mn\) 放在 \(p\) 的前面,这样 \(p\) 及后面的点造成的增加量必然不增。
然后如何实现找增加量最小的点?维护三个优先队列,保存 "当前矩形上/右/右上方" 的点。取出一个点之后打标记,以后不要在其他队列里取出来。
T3:
\(n\) 个数 \(\{s_i\}\) 任意分组,要求每一组极差的和 \(\le k\),求方案数。\(n\le 500,k\le 1000\)。
显然要排序,然后对于 \(s_i\) 有:单独开一组或者接在某组后面。
再细分,单独开一组立刻结束/单独开一组不结束/接在某组后面结束/接在某组后面不结束。
问题在于如果接在某组后面,每一组的结尾元素是不一定的,怎么找?
我们这么做:在加入 \(s_i\) 之后,剩下所有还没结束的组,贡献都增加 \(s_i-s_{i-1}\)。这相当于对贡献做了一个差分,然后一直做前缀和直到结束,刚好就是一组的贡献。
\(dp[i][j][sum]\) 表示考虑前 \(i\) 个,有 \(j\) 个还没结束的组,当前总和是 \(sum\) 的方案数。
T4:
有 \(n\) 个三元组,每个数的值域为 \(0\sim F\)。要求改最少的数,使每个三元组的总和递减。\(n\le 10^5,F\le 10^{10}\)。
初始想法:\(dp[i][j]\) 表示前 \(i\) 个三元组,第 \(i\) 个总和为 \(j\) 的方案数。\(dp[i][j]=\min dp[i-1][j\sim 3F]+dist(sum_i,j)\)。其中 \(sum_i\) 表示 \(i\) 初始的和,\(dist(sum_i,j)\) 表示改成 \(j\) 至少需要动几个数。
\(dist(i,j)\) 可以 \(O(1)\) 计算,这个复杂度是 \(O(nF^2)\) 的。
进阶想法:记录 \(mn[i][j]\) 为 \(dp[i]\) 的后缀 \(\min\),可以优化到 \(O(nF)\)。
满分想法:我们直接在枚举 \(i\) 的过程中维护 \(mn[i][]\) 的变化。用一个 map 维护 \(mn[i][]\) 的差分,即 \(mp[j]=mn[i][j]-mn[i][j-1]\)。再用一个变量维护 \(mn[i][0]\)。\(i\) 每次变动只有常数个位置变化。
标签:10,le,sum,mn,28,2024,某组,dp From: https://www.cnblogs.com/FLY-lai/p/18518164