1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
| #include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std;
typedef pair<int,int> pii; const int N=100,INF=1e9+7; pii operator +(pii a,pii b){return make_pair(a.first+b.first,a.second+b.second);}
struct GRAPH{ int head[N<<1],nxt[N*10],to[N*10],cap[N*10],cst[N*10],ncnt; GRAPH(){ncnt=1;} void AddEdge(int u,int v,int ca,int cs){ int p=++ncnt,q=++ncnt; nxt[p]=head[u],to[p]=v,cap[p]=ca,cst[p]=cs,head[u]=p; nxt[q]=head[v],to[q]=u,cap[q]=0,cst[q]=-cs,head[v]=q; } int operator [](const int &u){return head[u];} }Gr;
int n,m,S,T; int val[N],bok[N],las[N],dis[N<<1],head[N<<1]; bool inq[N<<1],vis[N<<1];
inline int Ri(){ register int r=0,c=getchar(); while(c<'0' || '9'<c) c=getchar(); while('0'<=c && c<='9') r=(r<<1)+(r<<3)+c-'0',c=getchar(); return r; } queue<int> que; bool SPFA(){ for(int i=1;i<=T;i++) head[i]=Gr[i],dis[i]=INF; que.push(S);dis[S]=0,inq[S]=true; while(!que.empty()){ int u=que.front();que.pop(); inq[u]=false; for(int it=Gr[u];it;it=Gr.nxt[it]){ int v=Gr.to[it]; if(Gr.cap[it]<=0 || dis[v]<=dis[u]+Gr.cst[it]) continue; dis[v]=dis[u]+Gr.cst[it]; if(!inq[v]) inq[v]=true,que.push(v); } } return dis[T]!=INF; } pii Aug(int u,int in){ if(u==T) return make_pair(in,0); pii res(0,0); vis[u]=true; for(int &it=head[u];it;it=Gr.nxt[it]){ int v=Gr.to[it]; if(vis[v] || Gr.cap[it]<=0 || dis[v]!=dis[u]+Gr.cst[it]) continue; pii tov=Aug(v,min(in-res.first,Gr.cap[it])); res=res+tov;res.second+=tov.first*Gr.cst[it]; Gr.cap[it]-=tov.first,Gr.cap[it^1]+=tov.first; if(res.first==in) break; } vis[u]=false; return res; } pii Dinic(){ pii res(0,0); while(SPFA()){ pii now=Aug(S,INF); res=res+now; } return res; } int main(){ n=Ri(),m=Ri(); for(int i=1;i<=n;i++) bok[i]=Ri(); for(int i=1;i<=n;i++) val[i]=Ri(); S=2*n+1,T=S+1; for(int i=1;i<=n;i++){ Gr.AddEdge(S,i,1,val[bok[i]]); Gr.AddEdge(i,i+n,1,0); Gr.AddEdge(i+n,T,1,0); if(i<n) Gr.AddEdge(i,i+1,m-1,0); } for(int i=1;i<=n;i++){ if(las[bok[i]]) Gr.AddEdge(i-1,las[bok[i]]+n,1,-val[bok[i]]); las[bok[i]]=i; }
printf("%d\n",Dinic().second); return 0; }
|