CodeForces

分析

首先将每天拆成两个点，入点 $s_i$ 和出点 $t_i$ 。

考虑怎么建图：

• 从源点向 $s_i$ 连容量为 $1$ 、费用为 $c_{a_i}$ 的边，表示每本书。
• 从 $s_i$ 向 $s_{i+1}$ 连容量为 $k-1$ 、费用为 $0$ 的边，表示第 $i$ 天最多留 $k-1$ 本书。
• 从 $s_i$ 向 $t_i$ 连容量为 $1$ 、费用为 $0$ 的边，表示买来就丢掉了这本书。
• 从 $s_{i-1}$ 向 $t_j$（ $j$ 表示上一个 $a_i$ 出现的位置）连容量为 $1$ 、费用为 $-c_{a_i}$ 的边，表示卖掉这本书。
• 从 $t_i$ 向汇点连容量为 $1$ 、费用为 $0$ 的边。

然后跑最小费用最大流，最小费用就是答案。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int inf=0x3f3f3f3f;

int n,k,s,t;
int a[100],c[100];
int pre[100];

struct Edge { int v,w,c,nxt; } e[1000010];
int head[100010];

inline void addEdge(int u,int v,int w,int c) {
    static int cnt=2;
    e[cnt]=(Edge){v,w,c,head[u]},head[u]=cnt++;
    e[cnt]=(Edge){u,0,-c,head[v]},head[v]=cnt++;
}

int dis[100010],inq[100010],last[100010];

inline int spfa() {
    memset(last,0,sizeof(last));
    memset(dis,0x3f,sizeof(dis)); dis[s]=0;
    queue<int> Q; Q.push(s); inq[s]=0;
    while (!Q.empty()) {
        int u=Q.front(); Q.pop(); inq[u]=0;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v;
            if (e[i].w&&dis[u]+e[i].c<dis[v]) {
                dis[v]=dis[u]+e[i].c,last[v]=i;
                if (!inq[v]) Q.push(v),inq[v]=1;
            }
        }
    }
    return last[t]!=0;
}

int main() {
    n=read(),k=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<=n;++i) c[i]=read();

    s=0,t=2*n+1;
    for (re int i=1;i<=n;++i) addEdge(s,i,1,c[a[i]]);
    for (re int i=1;i<=n;++i) addEdge(i,i+n,1,0);
    for (re int i=1;i<=n;++i) addEdge(i+n,t,1,0);
    for (re int i=1;i<n;++i) addEdge(i,i+1,k-1,0);
    for (re int i=1;i<=n;++i) {
        if (pre[a[i]]) addEdge(i-1,pre[a[i]]+n,1,-c[a[i]]);
        pre[a[i]]=i;
    }

    int ans=0;
    while (spfa()) {
        int f=inf;
        for (re int i=last[t];i;i=last[e[i^1].v]) f=min(f,e[i].w);
        for (re int i=last[t];i;i=last[e[i^1].v]) e[i].w-=f,e[i^1].w+=f;
        ans+=dis[t]*f;
    }
    printf("%d\n",ans);
    return 0;
}