キャッシュ戦略 题解

来源：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})$。

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