1

AGC034 D - Manhattan Max Matching

可以发现曼哈顿距离 (|x_1 - x_2| + |y_1 - y_2| = max(x_1 - x_2 + y_1 - y-2, x_1 - x_2 - y_1 + y_2, -x_1 + x_2 + y_1 - y_2, -x_1 + x_2 - y_1 + y_2)),

也就是合法即最大.

所以可以建四个点分别对应四种选择方案, 然后分别与红蓝点两边, 最大费用最大流即可.

考虑把所有字符都归位, 花费为 mincost, 那么之后每个字符都必须是"转圈", 所以可操作总数就是归位所需操作数 + (lfloor frac{maxcost - mincost}{c[1] + c[2] + c[3]} floor).

知道可操作总数后, 暴力的做法是设 (f[x][y][z]) 表示有 x 位已归位, 有 y 位还差一步, 有 z 位还差两步, 转移显然.

发现 (n = x + y + z), 所以可以压成二维, 状态数很小, 矩阵乘法优化即可.

注意不一定要花光总费用, 所以需要多开一位存答案.

正常的最长上升子序列设 (d[i]) 表示长度为 i 的上升子序列的结尾, (O(n log n)) 做就好

对于 (-1) , 枚举所有待选数更新 (d) , 可以先把待选数排序, 这样子两个序列就都具有单调性, 双指针更新就好

考虑构造方案, 对于有值的位置, 记录这个位置的值 (a[i]) 和以这个位置结尾的最长上升子序列的长度 (len[i])

从后往前构造最长上升子序列, 记构造到第 (i) 位 :

1.如果有有值的位置 (j) 满足 (j < i) 且 (a[j] < a[i]) 且 (len[j] = len[i] - 1), 那么就转移到 (j)

2.否则找到下一个 (-1), 填入最大的合法的待选数并转移到这一位

可以发现每个有值的位置都只会被用一遍, 且如果第一次需要用时它不合法, 那么之后也不会再合法了, 所以可以用链表之类的维护待用的有值位置

以及在开头结尾加极大极小值以避免某些细节。

(nowcoder) 上给了树形 (dp) 的壳但实际上是贪心的一道题。

首先考虑一种显然错误的贪心方法：从叶子节点往上染色，遇到白点就将其染黑，并往上染 (k) 个点。

观察一种一条链的情况，(k = ext{{1, 1, 3, 2}})，错误贪心会先染 (3), (4)，但是先染 (3) 再染 (4) 更优。由此可以得出正确的贪心的方法：

依然是从下往上，（长句警告！），每次遇到白点时我们考虑能否通过调整顺序使得先染其子树中的某一点以往上染尽可能多的点（显然我们并不会真正地模拟这一过程，只是这样形象地理解），简单地说，就是每次用 (k_u - 1) 更新 (k_{fa_u})。