Description：

一个容量为 $k$ 的书架，每次给定一本书 $a_i$ ，如果没有这本书就必须以 $c_i$ 的价格购买这本书放入书架。可以丢掉书架里的某本书。求出完成这 $n$ 个请求所需要的最少价钱。

$1\leqslant n\leqslant 80$

Solution：

和餐巾计划有点像，先拆点，把第 $i$ 天拆成 $v_i$ 和 $v_i'$ ，从源点向 $v_i$ 连容量为 $1$ 费用为 $c_i$ 的边，代表买入书，从 $v_i$ 向 $v_i'$ 连容量为 $1$ 费用为 $0$ 的边，代表把这本书直接卖掉，从 $v_i$ 向 $v_{i+1}$ 连容量为 $k-1$ 费用为 $0$ 的边，代表把书留下，最后也只最为重要的一步，从 $v_{i-1}$ 向 $v_{last[a_i]}'$ 连容量为 $1$ 费用为 $-c_i$ 的边，因为今天无论如何要买书，我们可以在前一天把它卖掉，因为同一本书最会卖一次，所以 $v_i'$ 到汇点连容量为 $1$ 费用为 $0$ 的边。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 200

int a[MAXN],c[MAXN],last[MAXN];

#define MAXP 400

#define MAXE (MAXN * 5)

struct edge

{

	int to,nxt,f,c;

}e[MAXE];

int edgenum = 0;

int lin[MAXP];

void add(int a,int b,int f,int c)

{

	e[edgenum] = (edge){b,lin[a],f,c};lin[a] = edgenum++;

	e[edgenum] = (edge){a,lin[b],0,-c};lin[b] = edgenum++;

	return;

}

int pre[MAXP],d[MAXP],rate[MAXP];

bool inq[MAXP];

int s,t;

#define INF 0x3f3f3f3f

bool SPFA()

{

    queue<int> q;q.push(s);

    memset(d,0x3f,sizeof(d));d[s] = 0;

    rate[s] = INF;

    while(!q.empty())

    {

        int k = q.front();q.pop();

        inq[k] = false;

        for(int i = lin[k];i != -1;i = e[i].nxt)

        {

            if(d[e[i].to] > d[k] + e[i].c && e[i].f)

            {

                d[e[i].to] = d[k] + e[i].c;

                pre[e[i].to] = i;

                rate[e[i].to] = min(rate[k],e[i].f);

                if(!inq[e[i].to])

                {

                    inq[e[i].to] = true;

                    q.push(e[i].to);

                }

            }

        }

    }

    return d[t] != INF;

}

int flow()

{

    for(int i = t;i != s;i = e[pre[i] ^ 1].to)

    {

        e[pre[i]].f -= rate[t];

        e[pre[i] ^ 1].f += rate[t];

    }

    return rate[t] * d[t];

}

int EK()

{

    int ans = 0;

    while(SPFA())ans += flow();

    return ans;

}

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d%d",&n,&m);

	s = 2 * n + 1;t = s + 1;

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	for(int i = 1;i <= n;++i)scanf("%d",&c[i]);

	for(int i = 1;i <= n;++i)add(s,2 * i - 1,1,c[a[i]]);

	for(int i = 1;i <= n;++i)

	{

		if(last[a[i]] != 0)add((i - 1) * 2 - 1,last[a[i]] * 2,1,-c[a[i]]);

		last[a[i]] = i;

		add(i * 2 - 1,i * 2,1,0);

		add(i * 2,t,1,0);

		if(i != n)add(i * 2 - 1,i * 2 + 1,m - 1,0);

	}

	cout << EK() << endl;

	return 0;

}