不妨看做是先用k个指针指向被选择的前k个元素，然后每次将选中当前第一个元素的指针移到最后，并且需要满足位置变化量>=m。显然这样可以构造出所有的合法方案。那么可以以此建立费用流模型，以一条流量k费用0的链将所有点串起来，再由每个位置向该位置+m连流量1费用为该元素权值的边，最大费用流即可。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define N 1010 #define S 0 #define T 1001 int n,m,k,p[N],t=-1,ans=0; int d[N],q[N],pre[N]; bool flag[N]; struct data{int to,nxt,cap,flow,cost; }edge[N<<4]; void addedge(int x,int y,int z,int c) { t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].cap=z,edge[t].flow=0,edge[t].cost=c,p[x]=t; t++;edge[t].to=x,edge[t].nxt=p[y],edge[t].cap=0,edge[t].flow=0,edge[t].cost=-c,p[y]=t; } int inc(int &x){x++;if (x>n+1) x-=n+1;return x;} bool spfa() { memset(d,42,sizeof(d));d[S]=0; memset(flag,0,sizeof(flag)); int head=0,tail=1;q[1]=S; do { int x=q[inc(head)];flag[x]=0; for (int i=p[x];~i;i=edge[i].nxt) if (d[x]+edge[i].cost<d[edge[i].to]&&edge[i].flow<edge[i].cap) { d[edge[i].to]=d[x]+edge[i].cost; pre[edge[i].to]=i; if (!flag[edge[i].to]) q[inc(tail)]=edge[i].to,flag[edge[i].to]=1; } }while (head!=tail); return d[T]<=0; } void ekspfa() { while (spfa()) { int v=n; for (int i=T;i!=S;i=edge[pre[i]^1].to) v=min(v,edge[pre[i]].cap-edge[pre[i]].flow); for (int i=T;i!=S;i=edge[pre[i]^1].to) ans-=v*edge[pre[i]].cost,edge[pre[i]].flow+=v,edge[pre[i]^1].flow-=v; } } int main() { #ifndef ONLINE_JUDGE freopen("bzoj1283.in","r",stdin); freopen("bzoj1283.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif n=read(),m=read(),k=read(); memset(p,255,sizeof(p)); for (int i=1;i<=n;i++) { int x=read(); addedge(i-1,i,k,0); addedge(i,i+m>n?T:i+m,1,-x); } addedge(n,T,k,0); ekspfa(); cout<<ans; return 0; }