キャッシュ戦略 题解

· · 题解

来源：utpc2011
编号：AT_utpc2011_8
tag：网络流建图
难度：紫

似乎好久没写题解了呢。

本文重点放在讲解为何是连边 x-1。

这是一个最优化问题。在原序列扫描的时候，dp 状态非常之多，要同时维护 m 个袋子的信息，所以不可行，随即考虑网络流。

对于两个相同且相邻的 a_i，可以看做是一个段，因为后面显然是直接继承前面的最优，代价为 0。这一步可以将序列强化成相邻两个元素不相等的情况。

显然结构是线性扫描。考虑如何建边。由于结构是线性扫描，只要考虑一个点从下一个点袋子信息的变化即可。不难想到由 m=1 的情况依次推到 m=M 的情况，所以求图上的费用流相当于求相对于 m=1 的代价所能省下的钱。可以建出 (i,i+1,M-1,0) 的边表示不为了下一个颜色而保留位置的情况。

问题在于为了下一个颜色而保留位置的情况。注意到从 x\to x+1 的转移上这些袋子中恰好存在一个下一个接受的元素是 x+1。也就是必须 强制 钦定某个转移是到 x+1 的。若边建成 pre_{a_x}\to x 且总流量若为 M 则不能保证必然存在一个 p=x+1，总流量若为 M-1 则如某些状态 1 2 1 2 会漏算掉某一个贡献，这是由于第一个 1 必须强制流到第二个 1，而在 2\to 3 时此时剩余的一个袋子可以让 2 保留到 4，但是原图中并不能从 3 流向 2。建成 pre_{a_x}\to x-1 则发现 x-1\to x 的边恰好可以被没有计入真正流量的第 1 条流流过。也就是，x\to x+1 所有流的实际意义是有若干 (\lt m) 个袋子是跨过 i+1 为更后面同颜色元素省钱， 剩下的流有一条是 恰好 为 i+1 保留的一个袋子，其他就是不需要留空间给后续元素的袋子。即连边 (pre_{a_x},x-1,1,-w_{a_x})。

submission

若有疑问和错误请指出，虚心接受您的意见。