CF802C

ltdj · 2022-02-17 11:28:56 · 题解

题解

这是一个只需要 n+2 个点的简单做法

如何想到

首先，容易想到的是：如果不能卖出再买入，对于一个颜色 x，我们在第一次出现买入，最后一次卖出。

上图，数轴上每个点表示一天，每天的书都可以直接流向下一天，容量为 k，费用为 0，表示放在书架。

问题是，如何考虑卖出后再买入的操作呢？

仔细想，对于相邻两个 x 之间的一段(如上图红色部分),这本书要么一直在书架，要么一直不在（如果前部分在后半部分不在还不如直接在上一个 x 那里卖掉）。如果不在书架的话，就不会占用书架的容量，但是在下一个 x 就一定要重新买。所以我们可以直接用一条额外的边连接相邻的两个 x,费用为 c_x,容量为 1。

为什么是对的

这样做是对的吗？我们发现：如果这样做不是错的话那它一定是对的（。我们考虑到错的情况有两种：一个流流过了它不该流的边或者不该流入的汇点。

1.我们称相邻两个 x 之间的边为购买边，理想状态下 x 只会走 x 的购买边，但实际上它可能走到 y 的购买边，由于购买边流量为1，此时 y 一定走的是书架边，那这种情况等价于 y 走购买边而 x 走书架边。所以，一条流只要从 x 第一次出现的点流入最后出现的点，那么中途无论经过什么边都是合法的

2.假如 x 流入了 y 的汇点呢？事实上由于第一点，下面两种情况可以看成等价的

而且它情况实际上都可以转化成上述情况的。

实现

有一个小细节，如果你完全按照上述建图，会有一个问题: 如果一个点刚买就卖了，他是不会走书架边的，但实际上它当天需要占用一个书架位置。那我们换一种思路，我们认为这本书是前一天下班的时候买的，把入边连到上一天即可。

int main()
{
    memset(head,-1,sizeof(head)); num_edge=-1;
    N=read(), K=read();
    for(int i=1; i<=N; i++) A[i]=read();
    for(int i=1; i<=N; i++) C[i]=read();
    s=N+1, t=N+2;

    for(int i=1; i<N; i++) addEdge(i, i+1, K, 0);
    for(int i=1; i<=N; i++){
        if(!VIS[A[i]]) {
            if(i == 1) addEdge(N+1, i, 1, C[A[i]]);
            else addEdge(N+1, i-1, 1, C[A[i]]);
        }else{
            addEdge(VIS[A[i]], i-1, 1, C[A[i]]);
        }
        VIS[A[i]] = i;
    }
    for(int i=1; i<=N; i++) if(VIS[i]) addEdge(VIS[i], N+2, 1, 0);
    MCMF();
    printf("%d\n", mincost);
    return 0;
}