BZOJ-1283: 序列

Description

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

网络流解线性规划问题。
直接链GXZlegend的BLOG:【bzoj1283】序列 线性规划与费用流
方程差分是解线性规划问题的精髓啊。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,k,s,t;
int head[1100],to[5000],nxt[5000],f[5000],w[5000],cnt=1;
inline void add(int x,int y,int z,int ww)
{
    to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z; w[cnt]=ww;
    to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0; w[cnt]=-ww;
}
int dis[1100],path[1100];
bool vis[1100];
queue<int>q;
bool spfa()
{
    memset(dis,0xef,sizeof dis);
    while(!q.empty()) q.pop();
    q.push(s); dis[s]=0; vis[s]=1; int x;
    while(!q.empty())
    {
        x=q.front(); q.pop(); vis[x]=0;
        for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]<dis[x]+w[i])
        {
            dis[to[i]]=dis[x]+w[i];
            path[to[i]]=i^1;
            if(!vis[to[i]]) vis[to[i]]=1,q.push(to[i]);
        }
    }
    return dis[t]>(int)0xefefefef;
}
int maxcost()
{
    int re=0;
    while(spfa())
    {
        int flow=inf;
        for(int i=t;i!=s;i=to[path[i]]) flow=min(flow,f[path[i]^1]);
        for(int i=t;i!=s;i=to[path[i]])
        {
            f[path[i]]+=flow; f[path[i]^1]-=flow;
            re+=flow*w[path[i]^1];
        }
    }
    return re;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k); s=0; t=n+1;
    int x; add(s,1,k,0);
    for(int i=1;i<=n;++i)
    {
        add(i,i+1,k,0);
        scanf("%d",&x);
        if(i+m>n) add(i,t,1,x);
        else add(i,i+m,1,x);
    }
    printf("%d",maxcost());
    return 0;
}