HDU 4106 Fruit Ninja 费用流

Fruit Ninja

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 629    Accepted Submission(s): 198

Problem Description

Fruit Ninja is a juicy action game enjoyed by millions of players around the world, with squishy, splat and satisfying fruit carnage! Become the ultimate bringer of sweet, tasty destruction with every slash.

Ali is very good at this game. He can cut every single fruit accurately if he wants. But after playing a long time, he became so tired that he cannot cut more than K fruit among any consecutively M fruit. But he also enjoys watching the fruit carnage, especially the one with big fruits. So he wants to maximum the total weight of the cut fruit.  

Input The input consists several testcases.

The first line contains three integer N, M, K (1 <= K <= M <= N <= 1000). N is the number of fruit, while M, K are described in the problem.

The second line contains N integers W 1 to W n (1 <= W i <= 10000), and W i represents the i-th fruit’s price.  

Output Print a real number, the maximum total weight of the cut fruit.

Sample Input

10 5 3
4 4 4 6 6 6 6 6 4 4
        

Sample Output

30
        

Source 2011 Alibaba-Cup Campus Contest

给出n个数的序列，选择一些数使总和最大。

对于任意长为m的区间中至多有k个数被选。

长为m共n-m+1个区间，选择一个点相当于覆盖了其中几个区间一次，每个区间最多被覆盖k次

建图就和poj3680一样了

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <list>
#include <stack>
#define ALL(v) (v).begin(),(v).end()
#define foreach(i,v) for (__typeof((v).begin())i=(v).begin();i!=(v).end();i++)
#define SIZE(v) ((int)(v).size())
#define mem(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define lp(k,a) for(int k=1;k<=a;k++)
#define lp0(k,a) for(int k=0;k<a;k++)
#define lpn(k,n,a) for(int k=n;k<=a;k++)
#define lpd(k,n,a) for(int k=n;k>=a;k--)
#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d %d",&a,&b)
#define lowbit(x) (x&(-x))
#define ll int
#define pi pair<int,int>
#define vi vector<int>
#define PI acos(-1.0)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define TT cout<<"*****"<<endl;
#define TTT cout<<"********"<<endl;

using namespace std;
#define inf 0x3f3f3f3f
#define Inf 0x3FFFFFFFFFFFFFFFLL
#define N 50000
#define M 50000

struct Edge
{
    ll to,cap,cost,nex;
    Edge() {}
    Edge(ll to,ll cap,ll cost,ll next):to(to),cap(cap),cost(cost),nex(next) {}
} edge[M];


ll head[N],top;
ll D[N],A[N],P[N],li[N];
bool inq[N];

void add(ll from,ll to,ll cap,ll cost)
{
    edge[top]=Edge(to,cap,cost,head[from]);
    head[from]=top++;
    edge[top]=Edge(from,0,-cost,head[to]);
    head[to]=top++;
}

bool spfa(ll s,ll t,ll &flow,ll &cost)
{
    for(ll i=0;i<=t;i++) D[i]=inf;
    mem(inq);
    queue<ll>q;
    q.push(s);
    D[s]=0;
    A[s]=inf;
    while(!q.empty())
    {
        ll u=q.front();
        q.pop();
        inq[u]=0;
        for(ll i=head[u];~i;i=edge[i].nex)
        {
            Edge &e=edge[i];
            if(e.cap && D[e.to]>D[u]+e.cost)
            {
                D[e.to]=D[u]+e.cost;
                P[e.to]=i;
                A[e.to]=min(A[u],e.cap);
                if(!inq[e.to])
                {
                    inq[e.to]=1;
                    q.push(e.to);
                }
            }
        }
    }
    if(D[t]==inf) return false;
    cost+=D[t]*A[t];
    flow+=A[t];
    ll u=t;
    while(u!=s)
    {
        edge[P[u]].cap-=A[t];
        edge[P[u]^1].cap+=A[t];
        u=edge[P[u]^1].to;
    }
    return true;
}

ll mcmf(ll s,ll t)
{
    ll flow=0, cost=0;
    while(spfa(s,t,flow,cost));
    return cost;
}

int a[N],S,T,n,m,k,re;
void init()
{
    mem1(head);
    top=0;
    S=0;
    T=n-m+3;
    lpn(i,0,n-m+1)
    {
        add(i,i+1,k,0);
    }
    lp(i,n)
    {
        int x=max(1,i-m+1);
        int y=min(i,n-m+1);
        add(x,y+1,1,-a[i]);
    }
     add(n-m+2,n-m+3,k,0);
}

int main()
{
   // freopen("in.txt","r",stdin);
    while(~scanf("%d %d %d",&n,&m,&k))
    {
        re=0;
        lp(i,n)
        {
            sc(a[i]);
            re+=a[i];
        }
        if(m<=k)
        {
            printf("%d\n",re);
            continue;
        }
        init();
        int cost=mcmf(S,T);
        printf("%d\n",-cost);
    }
    return 0;
}