学姐的逛街计划

题目链接：学姐的逛街计划

描述
doc 最近太忙了, 每天都有课. 这不怕, doc 可以请假不去上课.
偏偏学校又有规定, 任意连续 n 天中, 不得请假超过 k 天.

doc 很忧伤, 因为他还要陪学姐去逛街呢.

后来, doc发现, 如果自己哪一天智商更高一些, 陪学姐逛街会得到更多的好感度.
现在 doc 决定做一个实验来验证自己的猜想, 他拜托 小岛 预测出了 自己 未来 3n 天中, 每一天的智商.
doc 希望在之后的 3n 天中选出一些日子来陪学姐逛街, 要求在不违反校规的情况下, 陪学姐逛街的日子自己智商的总和最大.

可是, 究竟这个和最大能是多少呢?

格式
输入格式
第一行给出两个整数, n 和 k, 表示我们需要设计之后 3n 天的逛街计划, 且任意连续 n 天中不能请假超过 k 天.
第二行给出 3n 个整数, 依次表示 doc 每一天的智商有多少. 所有数据均为64位无符号整数

输出格式
输出只有一个整数, 表示可以取到的最大智商和.

样例1
样例输入1
5 3
14 21 9 30 11 8 1 20 29 23 17 27 7 8 35
Copy
样例输出1
195
Copy
限制
对于 20% 的数据, 1 <= n <= 12 , k = 3.
对于 70% 的数据, 1 <= n <= 40 .
对于 100% 的数据, 1 <= n <= 200 , 1 <= k <= 10.

bzoj原题。

我们通过问题转换：原问题等价于我们选k次，每次任意n个数当中只能选一个数字。

直接最大费用流。

我们直接让流量最大为k即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int inf=0x3f3f3f3f;
const int N=610,M=1e5+10;
int n,m,k,s,t,d[N],v[N],e[N],a[N];
int head[N],nex[M],to[M],w[M],flow[M],tot=1;
inline void ade(int a,int b,int c,int d){
	to[++tot]=b; nex[tot]=head[a]; w[tot]=d; flow[tot]=c; head[a]=tot;
}
inline void add(int a,int b,int c,int d){ade(a,b,c,d); ade(b,a,0,-d);}
inline int spfa(){
	memset(d,0xcf,sizeof d); d[s]=0; int vis[N]={0}; vis[s]=1;
	queue<int> q;	q.push(s);
	while(q.size()){
		int u=q.front();	q.pop(); vis[u]=0;
		for(int i=head[u];i;i=nex[i]){
			if(flow[i]&&d[to[i]]<d[u]+w[i]){
				d[to[i]]=d[u]+w[i];
				v[to[i]]=u; e[to[i]]=i;
				if(!vis[to[i]])	q.push(to[i]),vis[to[i]]=1;
			}
		}
	}
	return d[t]!=0xcfcfcfcf;
}
int EK(){
	int res=0;
	while(spfa()){
		int mi=inf;
		for(int i=t;i!=s;i=v[i])	mi=min(flow[e[i]],mi);
		for(int i=t;i!=s;i=v[i])	flow[e[i]]-=mi,flow[e[i]^1]+=mi;
		res+=d[t]*mi;
	}
	return res;
}
signed main(){
	cin>>n>>k; m=n*3; t=m+1;
	for(int i=1;i<=m;i++)	cin>>a[i];
	add(s,1,k,0); add(m,t,k,0);
	for(int i=1;i<m;i++)	add(i,i+1,k,0);
	for(int i=1;i<=m-n;i++)	add(i,i+n,1,a[i]);
	for(int i=m-n+1;i<=m;i++)	add(i,t,1,a[i]);
	cout<<EK()<<endl;
	return 0;
}