bzoj 1283_牛客博客

1283: 序列
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 687 Solved: 398

Description
给出一个长度为 N 的正整数序列Ci，求一个子序列，使得原序列中任意长度为 M 的子串中被选出的元素不超过K(K,M<=100) 个，并且选出的元素之和最大。

Input
第1行三个数N,m,k。接下来N行，每行一个字符串表示Ci。

Output
最大和。

Sample Input
10 5 3

4 4 4 6 6 6 6 6 4 4

Sample Output
30

HINT
20%的数据:n<=10。
100%的数据：N<=1000，k,m<=100。Ci<=20000。

一道费用流的题目。看到这道题，一般很难想到去用网络流求解。这道题也是出现在了许多国家集训队论文中。

考虑题目：题意可等价于，我们去取k次，每次只能取一个数字，并且，任意长度为m的子序列当中，只能取一个数字。不难证明原问题的一种合法方案，再转化之后具有同样的合法方案。

考虑建图：我们单独建立源点S和汇点T。
我们让 1 到 n-1 的每个数字连一条指向后面数字的边，流量为k，费用为0,。
让S连向1，流量为k，费用为0,；让n连向T，流量为k，费用为0；
对于 1 到 n-m 的每个数字，我们连一条 i 指向 i+m 的边，流量为1，费用为 c[i] 。
对于 n-m+1 到 n 的每个数字，我们连一条 i 指向 T 的边，流量为1 ，费用为 c[i] 。

最后直接求S到T的最大费用最大流即可。

AC代码：

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