Vijos1891 学姐的逛街计划

描述

doc 最近太忙了, 每天都有课. 这不怕, doc 可以请假不去上课.

偏偏学校又有规定, 任意连续 n 天中, 不得请假超过 k 天.

doc 很忧伤, 因为他还要陪学姐去逛街呢.

后来, doc发现, 如果自己哪一天智商更高一些, 陪学姐逛街会得到更多的好感度.

现在 doc 决定做一个实验来验证自己的猜想, 他拜托小岛预测出了自己未来 3n 天中, 每一天的智商.

doc 希望在之后的 3n 天中选出一些日子来陪学姐逛街, 要求在不违反校规的情况下, 陪学姐逛街的日子自己智商的总和最大.

可是, 究竟这个和最大能是多少呢?

格式

输入格式

第一行给出两个整数, n 和 k, 表示我们需要设计之后 3n 天的逛街计划, 且任意连续 n 天中不能请假超过 k 天.

第二行给出 3n 个整数, 依次表示 doc 每一天的智商有多少. 所有数据均为64位无符号整数

输出格式

输出只有一个整数, 表示可以取到的最大智商和.

样例1

样例输入1

5 3

14 21 9 30 11 8 1 20 29 23 17 27 7 8 35

样例输出1

195

限制

对于 20% 的数据, 1 <= n <= 12 , k = 3.

对于 70% 的数据, 1 <= n <= 40 .

对于 100% 的数据, 1 <= n <= 200 , 1 <= k <= 10.

将每个点拆成i和i’，从S向SS连容量为k费用为0的边，SS向每个点i连容量为1费用为0的边，每个i向i’连容量为1费用为价值的边，每个i’向T连容量为1费用为0的边，i’向[i+n,i+n*3]中的所有点连容量为1费用为0的边，跑最大费用流。

" role="presentation"> —by Milky Way

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=2010;

const LL INF=1e18;

LL read(){

    LL ans=0,w=1;char c=getchar();

    while(!isdigit(c)&&c!='-')c=getchar();

    if(c=='-')c=getchar(),w=-1;

    while(isdigit(c))ans=ans*10+c-'0',c=getchar();

    return ans*w;

}

struct Edge{

    int from,to;

    LL flow,cap,cost;

}E[N*N>>2];

vector<int> G[N];

int S,SS,T,n,tot=0,p[N];

LL d[N],f[N];

bool inq[N];

void add(int from,int to,LL cap,LL cost){

    E[tot]=(Edge){from,to,0,cap,cost};

    G[from].push_back(tot++);

    E[tot]=(Edge){to,from,0,0,-cost};

    G[to].push_back(tot++);

}

bool SPFA(LL &flow,LL &cost){

    memset(inq,0,sizeof(inq));

    queue<int> q;q.push(S);

    inq[S]=1;

    for(int i=1;i<=T;i++)d[i]=INF;

    d[S]=p[S]=0,f[S]=INF;

    while(!q.empty()){

        int x=q.front();q.pop();inq[x]=0;

        for(int i=0;i<G[x].size();i++){

            Edge e=E[G[x][i]];

            if(e.cap>e.flow&&d[e.to]>d[x]+e.cost){

                d[e .to]=d[x]+e.cost;

                p[e.to]=G[x][i];//记录经过哪条边

                f[e.to]=min(f[x],e.cap-e.flow);

                if(!inq[e.to])q.push(e.to),inq[e.to]=1;

            }

        }

    }

    if(d[T]==INF)return false;

    flow+=f[T],cost+=f[T]*d[T];

    int x=T;

    while(x!=S){

        E[p[x]].flow+=f[T];

        E[p[x]^1].flow-=f[T];

        x=E[p[x]].from;

    }

    return true;

}

LL mincost(){

    LL flow=0,cost=0;

    while(SPFA(flow,cost)){}

    return cost;

}

int main(){

    n=read();int k=read();

    S=0,SS=n*6+1,T=SS+1;

    add(S,SS,k,0);

    for(int i=1;i<=n*3;i++){

        int x=read();

        add(SS,i,1,0);

        add(i,i+n*3,1,-x);

        add(i+n*3,T,1,0);

        for(int j=i+n;j<=n*3;j++)

            add(i+n*3,j,1,0);

    }

    printf("%lld\n",-mincost());

    return 0;

}

逛街