题解：【AT_utpc2011_8】キャッシュ戦略

My_Youth · 2023-03-17 13:15:57 · 题解

题目链接

机翻多少有点生草，不如重新描述一遍。总共有 m 个盒子，给定 n 种 k 个小球，依次放入盒子中，求最小的花费。花费定义为对于第 i 个小球：

如果已经有盒子放有这种小球，则代价为 0。
如果没有盒子有这种小球，则花费 w_{a_i} 的代价找一个盒子放下，如果选的这个盒子里有球，则拿出之前放的球。

首先连续插入同一种小球的情况是平凡的，所以可以在读入的时候把连续颜色段缩成一个。

记同一种小球当前插入时间为 s，下一次插入时间为 t，那么实际决策只有两种：

无论在 [s,t) 的哪个时刻取出小球，对答案的贡献都是相同的，所以不妨钦定放入后立即取出，即 s 放入，s + 1 拿出，代价为 w_{a_i}。
一直放在盒子中直到下一次插入，这样下一次插入代价为 0。

首先我们假设每个小球都用第一种决策，然后再看怎样尽可能多的选决策二替代决策一。

考虑费用流。以下记当前位置为 i ，对于在 i 的这种小球，上一次出现的位置为 pre_i，源点为 s，汇点为 t。

对于第一种决策，我们连 i \to i + 1，费用为 0，流量为 \text{INF} 即没有节省代价，放入 i 的小球后在 i + 1 接着拿出。
对于第二种决策，我们连 pre_i + 1 \to i 表示上一次放入后不在 pre_i + 1 拿出，而是一直放置到 i 这个位置，费用为 - w_{a_i} 表示能省下 w_{a_i}，流量自然为 1。
最后连 s \to 1，k \to t。限定 s \to 1 的流量为 m-1。

为什么这样限定流量呢？考虑这里流量的含义是盒子被使用的状况。因为我们要保证始终有一个盒子可以让我们进行决策一的瞬间放入拿出，所以我们同一时刻最多只能有 m - 1 个盒子存着之前的小球。

对于上面一串的建边，当然还有一张感性一些的图。

黑色代表决策一，彩色代表可以选择的决策二，我们在一个时刻不能同时占用超过 m-1 个盒子，使得不能操作决策一。

时间复杂度 \mathcal O(K M (N + K))，由于 M 很小，上来就很限制流量，所以远远达不到这个上界。

这个题也算得上是上古题了，官方题解给的十分简略模糊，再加上 AtCoder 上这个题的评测还写的有点锅，所以有很多奇怪的问题。首先是最后输出答案必须要加一个换行，不然会判定收不到答案一直时间超限。还有就是要开 \text{int}，笔者~~因为代码丑陋~~不用 \text{int} 也会超时。

#include<bits/stdc++.h>
using namespace std;

inline int read()
{
    int s=0,w=1;
    char c=getchar();
    while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
    while(isdigit(c)) s=(s<<1)+(s<<3)+(c^48),c=getchar();
    return s*w;
}

namespace LgxTpre
{
    static const int MAX=100010;
    static const int INF=2007070707;
    static const int mod=998244353;

    int m,n,k,x;
    int sum,con;
    int w[MAX],a[MAX],lst[MAX];

    struct edge
    {
        int nex,to,val,flow;
    }e[MAX<<1];
    int head[MAX],cnt=1;
    inline void add(int x,int y,int val,int flow)
    {
        e[++cnt].nex=head[x],head[x]=cnt,e[cnt].to=y,e[cnt].val=val,e[cnt].flow=flow;
        e[++cnt].nex=head[y],head[y]=cnt,e[cnt].to=x,e[cnt].val=-val,e[cnt].flow=0;
        return;
    }

    int s,t;
    int incf[MAX],dis[MAX],vis[MAX],pre[MAX];   
    int maxflow,mincost;
    queue<int> q;
    inline bool spfa()
    {
        for(int i=s;i<=t;++i) vis[i]=0,dis[i]=INF;
        q.push(s),vis[s]=1,dis[s]=0,incf[s]=INF;
        while(!q.empty())
        {
            int now=q.front(); q.pop();
            vis[now]=0;
            for(int i=head[now];i;i=e[i].nex)
            {
                int to=e[i].to;
                if(!e[i].flow) continue;
                if(dis[to]>dis[now]+e[i].val)
                {
                    dis[to]=dis[now]+e[i].val;
                    incf[to]=min(e[i].flow,incf[now]);
                    pre[to]=i;
                    if(!vis[to]) vis[to]=1,q.push(to);
                }
            }
        }
        return dis[t]!=INF;
    }
    inline void Augment()
    {
        while(spfa())
        {
            int now=t;
            maxflow+=incf[t];
            mincost+=incf[t]*dis[t];
            while(now!=s)
            {
                int i=pre[now];
                e[i].flow-=incf[t];
                e[i^1].flow+=incf[t];
                now=e[i^1].to;
            }
        }
        return;
    }

    inline void lmy_forever()
    {
        m=read(),n=read(),k=read();
        for(int i=1;i<=n;++i) w[i]=read();
        for(int i=1;i<=k;++i) {x=read(); if(a[con]!=x) a[++con]=x;}
        k=con,s=0,t=k+1;
        for(int i=1;i<=k;++i)
        {
            if(i!=k) add(i,i+1,0,INF);
            if(lst[a[i]]) add(lst[a[i]]+1,i,-w[a[i]],1);
            lst[a[i]]=i;
            sum+=w[a[i]];
        }
        add(s,1,0,m-1),add(k,t,0,INF);
        Augment();
        printf("%d\n",mincost+sum);
        return;
    }
}

signed main()
{
    LgxTpre::lmy_forever();
    return (0-0);
}