题目大意：给定一个长度为n的序列，要求选一些数，使得任意一个长度为m个区间中最多选k个数，，求最大的和
费用流直接跑就是了
把这个序列用流量为k费用为0的边连成一条直线 然后第i个点向第i+m个点连一条费用为a[i]流量为1的边
跑最大费用最大流即可
卡单纯型差评。。。。
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 1010#define S 0#define T (M-1)#define INF 0x3f3f3f3fusing namespace std;int n,m,k,ans;int a[M];namespace Max_Cost_Max_Flow{struct abcd{int to,flow,cost,next;}table[1001001];int head[M],tot=1;void Add(int x,int y,int f,int c){table[++tot].to=y;table[tot].flow=f;table[tot].cost=c;table[tot].next=head[x];head[x]=tot;}void Link(int x,int y,int f,int c){Add(x,y,f,c);Add(y,x,0,-c);}bool Edmonds_Karp(){static int q[65540],flow[M],cost[M],from[M];static unsigned short r,h;static bool v[M];int i;memset(cost,0xef,sizeof cost);q[++r]=S;cost[S]=0;flow[S]=INF;while(r!=h){int x=q[++h];v[x]=false;for(i=head[x];i;i=table[i].next)if(table[i].flow&&cost[table[i].to]<cost[x]+table[i].cost){cost[table[i].to]=cost[x]+table[i].cost;flow[table[i].to]=min(flow[x],table[i].flow);from[table[i].to]=i;if(!v[table[i].to])v[table[i].to]=true,q[++r]=table[i].to;}}if(cost[T]==0xefefefef) return false;ans+=flow[T]*cost[T];for(i=from[T];i;i=from[table[i^1].to])table[i].flow-=flow[T],table[i^1].flow+=flow[T];return true;}}int main(){using namespace Max_Cost_Max_Flow;int i;cin>>n>>m>>k;for(i=1;i<=n;i++)scanf("%d",&a[i]);for(i=1;i<=n;i++){Link(i-1,i,k,0);if(i+m<=n)Link(i,i+m,1,a[i]);elseLink(i,T,1,a[i]);}Link(n,T,k,0);while( Edmonds_Karp() );cout<<ans<<endl;return 0;}
问候不一定要慎重其事，但一定要真诚感人
