2015
04-16

# Fruit Ninja

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.

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 W1 to Wn (1 <= Wi <= 10000), and Wi represents the i-th fruit’s price.

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 W1 to Wn (1 <= Wi <= 10000), and Wi represents the i-th fruit’s price.

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

30

max(1,i-m+1) ；right = min(i,tot-1)+1;分别是每个点对区间限制的左边界和又边界，那么就完成了转换！和poj 3680一样，从源点连接一条边到1，容量k，费用0，第 n – m + 2 个点连一条边道汇点 end，容量 k ，费用0，然后交换了正向和逆向的费用之后就是最小费费用流！这种模型的具体方法可以看 http://blog.csdn.net/zz_1215/article/details/7270630

#include<iostream>
#include<vector>
#include<cstring>
#include<string>
#include<cstdio>
#include<iomanip>
#include<queue>
#include<map>
#include<stack>
#include<cassert>
#include<algorithm>
using namespace std;

const int maxn = 1024;
const int end = 1023;
const int inf = 0x3f3f3f3f;

struct zz
{
int from;
int to;
int c;
int cost;
int id;
}zx,tz;

int w[maxn];
vector<zz>g[maxn];
bool inq[maxn];
queue<int>q;
int way[maxn];
bool vis[maxn];
int backid[maxn];
int n,m,k,tot,minflow,sum;

void link(int now,int to,int c,int cost,int bc,int bcost)
{
zx.from = now;
zx.to = to;
zx.c = c;
zx.cost = cost;
zx.id = g[to].size();
g[now].push_back(zx);
swap(zx.from , zx.to);
zx.c = bc;
zx.cost = bcost;
zx.id = g[now].size() - 1;
g[zx.from].push_back(zx);
return ;
}

bool spfa()
{
while(!q.empty())
{
q.pop();
}
memset(inq,false,sizeof(inq));
memset(backid,-1,sizeof(backid));
for(int i=1;i<=tot;i++)
{
way[i] = inf;
}
way[end] = inf;
way[0] = 0;
inq[0] = true;
q.push(0);
int now,to,cost,id,temp;
while(!q.empty())
{
now = q.front();
q.pop();
for(int i=0;i<g[now].size();i++)
{
if(g[now][i].c > 0)
{
to = g[now][i].to;
id = g[now][i].id;
cost = g[now][i].cost;
temp = way[now] + cost;
if(temp < way[to])
{
backid[to] = id;
//   assert(g[to][id].to == now)
way[to] = temp;
if(!inq[to])
{
q.push(to);
inq[to] = true;
}
}
}
}
inq[now] = false;
}
minflow = inf;
int nowid;
temp = end;
while(backid[temp] != -1)
{
id = backid[temp];
now = g[temp][id].to;
nowid = g[temp][id].id;
minflow = min(g[now][nowid].c , minflow);
temp = now;
}
temp = end;
while(backid[temp] != -1)
{
id = backid[temp];
now = g[temp][id].to;
nowid = g[temp][id].id;
g[now][nowid].c -= minflow;
g[temp][id].c += minflow;
temp = now;
}
if(way[end] < 0)
{
return true;
}
else
{
return false;
}
}

int EK()
{
int ans=0;
while( spfa() )
{
ans += way[end]*minflow;
}
return -ans;
}

int main()
{
while(scanf("%d%d%d",&n,&m,&k) != EOF)
{
sum = 0;
for(int i=0;i<maxn;i++)
{
g[i].clear();
}
for(int i=1;i<=n;i++)
{
//  cin>>w[i];
scanf("%d",&w[i]);
sum += w[i];
}
//   assert(m > k);
if(m<=k)
{
printf("%d\n",sum);
//    cout<<sum<<endl;
continue;
}
tot = n - m + 2;
for(int i=1; i<tot; i++)
{
}
int now,to;
for(int i=1;i<=n;i++)
{
now = max(1,i-m+1);
to = min(i,tot-1)+1;