#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
#include <thread>
using namespace std;

namespace dts
{
    typedef long long ll;
    
    double oo_min=(numeric_limits<double>::min)(),oo_max=(numeric_limits<double>::max)();
    
    struct network_flows
    {
        vector<ll> e;
        vector<ll> pre;
        vector<ll> vis;
        vector<vector<ll> > cw;
        vector<vector<ll> > ce;
        vector<double> f;
        vector<double> u;
        vector<vector<double> > c;
        vector<vector<double> > p;
        deque<ll> q;
        
        void clear_flow()
        {
            e.clear();
            pre.clear();
            vis.clear();
            f.clear();
            u.clear();
        }
        
        void clear_edge()
        {
            clear_flow();
            cw.clear();
            ce.clear();
            c.clear();
            p.clear();
        }
        
        ll size()
        {
            return cw.size();
        }
        
        void set_size(ll size_v)
        {
            clear_edge();
            cw.resize(size_v);
            ce.resize(size());
            c.resize(size());
            p.resize(size());
        }
        
        void add_edge(ll x,ll y,double c_v,double p_v)
        {
            cw[x].push_back(y);
            c[x].push_back(c_v);
            p[x].push_back(p_v);
            ce[y].push_back(cw[x].size()-1);
            cw[y].push_back(x);
            c[y].push_back(0);
            p[y].push_back(-p_v);
            ce[x].push_back(cw[y].size()-1);
        }
        
        void prepare(ll s,ll t)
        {
            clear_flow();
            f.resize(size(),0);
            f[s]=oo_max;
            e.resize(size(),-1);
            u.resize(size(),oo_max);
            u[s]=0;
            pre.resize(size(),-1);
            pre[s]=s;
            vis.resize(size(),0);
        }
        
        ll bfs(ll s,ll t,double &flow,double &cost)
        {
            prepare(s,t);
            for (q.clear(),vis[s]=1,q.push_back(s);!q.empty();vis[q.front()]=0,q.pop_front())
            {
                ll now=q.front();
                for (ll i=0;i<cw[now].size();i++)
                    if (c[now][i]>0&&u[now]+p[now][i]<u[cw[now][i]])
                    {
                        f[cw[now][i]]=min(c[now][i],f[now]);
                        e[cw[now][i]]=i;
                        u[cw[now][i]]=u[now]+p[now][i];
                        pre[cw[now][i]]=now;
                        if (vis[cw[now][i]]==0)
                            vis[cw[now][i]]=1,q.push_back(cw[now][i]);
                    }
            }
            flow=f[t];
            cost=u[t];
            return (pre[t]!=-1);
        }
        
        void min_cost_max_flow(ll s,ll t,ll typ,double &flow,double &cost)
        {
            double temp_flow,temp_cost;
            while (bfs(s,t,temp_flow,temp_cost))
            {
                for (ll i=t;i!=s;i=pre[i])
                    c[pre[i]][e[i]]-=temp_flow,c[i][ce[pre[i]][e[i]]]+=temp_flow;
                flow+=temp_flow;
                if (typ==0)
                    cost+=temp_cost;
                else if (typ==1)
                    cost+=(temp_flow*temp_cost);
            }
        }
    }net;
    
    ll n,m,t;
    vector<double> a;
    
    void main()
    {
        while (~scanf("%lld%lld%lld",&n,&m,&t))
        {
            a.clear();
            a.resize(n+1,0);
            for (int i=1;i<=n;i++)
                scanf("%lf",&a[i]);
            net.set_size(n-m+4);
            net.add_edge(0,1,t,0);
            net.add_edge(net.size()-2,net.size()-1,t,0);
            net.add_edge(1,net.size()-2,1,0);
            for (int i=1;i<=m;i++)
                net.add_edge(1,i+1,1,-a[i]);
            for (int i=n-m+1;i<=n;i++)
                net.add_edge(i-m+1,net.size()-2,1,-a[i]);
            for (int i=m+1;i<=n-m;i++)
                net.add_edge(i-m+1,i+1,1,-a[i]);
            for (int i=1;i<=n-m+1;i++)
                net.add_edge(i,i+1,oo_max,0);
            double ans_flow=0,ans_cost=0;
            net.min_cost_max_flow(0,net.size()-1,0,ans_flow,ans_cost);
            printf("%.0lf\n",-ans_cost);
        }
    }
};

int main()
{
    dts::main();
}

研究了一天终于懂了 参考的是楼下boyzkk大神

下面以N=5，M=2为例
c[1]+c[2]<=k
c[2]+c[3]<=k
c[3]+c[4]<=k
c[4]+c[5]<=k
变换得
c[1]+c[2]+y[1]-k=0
c[2]+c[3]+y[2]-k=0
c[3]+c[4]+y[3]-k=0
c[4]+c[5]+y[4]-k=0

添加0式为空，5式为空
前-后得
c[1]-c[2]+y[1]-k=0
c[3]-c[1]+y[2]-y[1]=0
c[4]-c[2]+y[3]-y[2]=0
c[5]-c[3]+y[4]-y[3]=0
-c[4]-c[5]-y[4]+k=0

对于任意变量，在所有式子中均只出现两次，且一正一负，就像【流量平衡】
于是把正数看做入流，负数看做出流，把每个式子抽象成一个点，连边
比如①中有正C[1]，②中有-C[1]，那么由①向②连一条流量为1，费用为a[1]的边
对于常数K，移向等号右边，那么由S向①式连一条流量为K，费用为0的边
由⑤向T连一条流量为K，费用为0的边
这是我的建图
S=0; tot=n-m+2; T=tot+1;
add(S,1,K,0); add(tot,T,K,0);
add(1,tot,1,0);
for (int i=1;i<=m;++i) add(1,i+1,1,a[i]);
for (int i=n-m+1;i<=n;++i) add(i-m+1,tot,1,a[i]);
for (int i=m+1;i<=n-m;++i) add(i-m+1,i+1,1,a[i]);
for (int i=1;i<=n-m+1;++i) add(i,i+1,inf,0);

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

1次AC, 唯一缺憾的是第13次提交...

说一下解法:

c[i]表示第i件物品选与不选, 取值在[0,1].

那么会有原始不等式:

c[1]+c[2]+...+c[m]

如果写过Employee的话，只要知道把每个物品当作选或者不选（0或1）来看待就好了
x1+x2+...+xm-y1=k ..然后小心各种样例数据坑人，最好能自己手写一组去试试建边
可以试试 n=13,m=3 k和下面那些数字无所谓，只是为了搞明白怎么建边

70行的 朴素 单纯型…………

编译通过...

├ 测试数据 01：答案正确... 852ms

├ 测试数据 02：答案正确... 134ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：运行超时...

├ 测试数据 05：答案正确... 274ms

├ 测试数据 06：运行超时...

├ 测试数据 07：答案正确... 508ms

├ 测试数据 08：运行超时...

├ 测试数据 09：运行超时...

├ 测试数据 10：答案正确... 321ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：60 有效耗时：2089ms

话说我自己机子极限 随机数据是能过的…………

如果不是vag 6k，说不定不优化就能过了……

编译通过...

├ 测试数据 01：答案正确... 321ms

├ 测试数据 02：答案正确... 134ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 290ms

├ 测试数据 06：答案正确... 524ms

├ 测试数据 07：答案正确... 25ms

├ 测试数据 08：答案正确... 789ms

├ 测试数据 09：答案正确... 462ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2545ms

加了一行贪心优化之后，依然是vag 6k………

弱弱地问一句……什么叫线性规划（DP吗），我只知道这个题是费用流……

求数据……

有的好心人发我邮箱吧:NWintre@163.com

thx

线性规划，重在构图。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 56ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 9ms

├ 测试数据 06：答案正确... 9ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 56ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：130ms

我是傻X，让这题通过率狂掉………………

模型类似于employee，但建图真的很讨厌…………交了8次，每次建图都不一样……………… - -!

后来发现都是些傻瓜错误，囧。

我就好心的发一下建图方法吧：

add(st,1,K,0);

add(n-m+2,en,K,0);

for(i=1;i=n-m+2) add(1,n-m+2,1,a[i]);

else add(1,i+1,1,a[i]);

for(i=2;i=n-m+2) add(i,n-m+2,1,a);

else add(i,i+m,1,a);

for(i=1;i

编译通过...

├ 测试数据 01：答案正确... 322ms

├ 测试数据 02：答案正确... 197ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 541ms

├ 测试数据 06：答案正确... 197ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 353ms

├ 测试数据 09：答案正确... 228ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1838ms

囧RZ

弱弱的我感慨：这题很强大，orz...

编译通过...

我是一个菜鸟。。。。。

我用搜索与回溯做超时了。

该怎么优化

先开始队列尾循环，头忘循环循环，10分。

后来改成循环，Accept。

要用链表或者前向星存边,不习惯,不想写了

我太沙茶了，边容量是1，搞成maxlongint了

谁来罩我把,为什么这题像1525那样构图只有60分.

vijos不能添加新题了，voyagec2就覆盖了老题，不好意思啊。

注意题目是绝对值小于1000，如果用zkw费用流必须要先做一次SPFA，否则处理负权边会出问题。

谁偷了我的号！！！！！

这个题目不是我加的！！

此题建图方法不同会导致时间相差极大。

ufo172849z沙茶建图用spfa不能秒杀。oimaster的神new建图用spfa秒杀。