BZOJ 1283 序列

题目大意

给出一个长度为$n$的正整数序列$C_i$，求一个子序列，使得原序列中任意长度为$m$的子串中被选出的元素不超过$k$($k,m \le 100$) 个，并且选出的元素之和最大。

费用流好题。

任意长度为$m$的子串中被选出元素不超过$k$个这一条件可以转化成任意长度为$m$的子串中被选出元素不超过$1$个，选择$k$次，每次的选择不同。之后进行网络流建图：$S$向$1$连边，容量$k$，费用$0$，表示初始的$n$次选择；$i$向$i+1$连边，容量$k$，费用$0$，表示不选$i$的情况下流量去向；$i$向$i+m$连边，容量$1$，费用$C_i$，表示选$i$的流量走向；$+ m \gt n$的点向T连边，容量1，费用$C_i$，表示最后选这个点。这样可以保证每个点每次选择只选一次，而且保证一个点选择之后在该次选择中和它距离$\le m$的点不会被选择。

之后跑最大费用最大流即可，注意初始值= =

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1100
#define M 500000
#define INF (1<<30)
int n,m,k,S,T,c[N],pre[N],frm[N],dis[N],ans;
int to[M],nxt[M],val[M],cst[M],head[N],tot=1;
queue<int>q;
inline void AE(int x,int y,int a,int b)
{
	to[++tot]=y,nxt[tot]=head[x],head[x]=tot,val[tot]=a,cst[tot]=b;
	to[++tot]=x,nxt[tot]=head[y],head[y]=tot,val[tot]=0,cst[tot]=-b;
}
bool SPFA()
{
	q.push(S);
	memset(dis,0xf7,sizeof dis),dis[S]=0;
	while(!q.empty())
	{
		int pos=q.front();q.pop();
		for(int i=head[pos];i;i=nxt[i])
			if(val[i]&&dis[to[i]]<dis[pos]+cst[i])
			{
				dis[to[i]]=dis[pos]+cst[i];
				frm[to[i]]=pos,pre[to[i]]=i;
				q.push(to[i]);
			}
	}
	return dis[T]!=0xf7f7f7f7;
}
int main()
{
	scanf("%d%d%d",&n,&m,&k),S=0,T=n+1;
	for(int i=1;i<=n;++i) scanf("%d",c+i);
	AE(S,1,k,0);
	for(int i=2;i<=n;++i) AE(i-1,i,k,0);
	for(int i=1;i<=n;++i) AE(i,min(T,i+m),1,c[i]);
	while(SPFA())
	{
		int tmp=INF;
		for(int i=T;i!=S;i=frm[i]) tmp=min(tmp,val[pre[i]]);
		ans+=tmp*dis[T];
		for(int i=T;i!=S;i=frm[i]) val[pre[i]]-=tmp,val[pre[i]^1]+=tmp;
	}
	printf("%d\n",ans);
	return 0;
}