首页 > ACM题库 > HDU-杭电 > HDU 4106-Fruit Ninja-分治-[解题报告]HOJ
2015
04-16

HDU 4106-Fruit Ninja-分治-[解题报告]HOJ

Fruit Ninja

问题描述 :

Electric wave

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

准确的说这道题已经卡了我3个月了,3个月前我还是连spfa都写不好的小菜鸟,3个月前我还在刷水dp,3个月前写个水二分都会出错,3个月前我很无力。。。转眼,经过一个寒假的训练,虽然还是菜鸟,但也算得上是一个犀利的菜鸟了有木有!!

这题是poj 3680的一个变形,分析下,poj 3680 是区间对点的限制!!!而这道题,是点对区间的限制!!!如果选取取一个数,那么每个包含这个数且长度为 M 的连续区间内可以选的数都要减少一个,对吧?转换模型!点变区间,区间变点!把区间离散化为 n – m + 1个部分,那么就有 n – m + 2 个点,left =
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++)
        {
            link(i,i+1,inf,0,0,0);
        }
        link(0,1,k,0,0,0);
        link(tot,end,k,0,0,0);
        int now,to;
        for(int i=1;i<=n;i++)
        {
            now = max(1,i-m+1);
            to = min(i,tot-1)+1;
            link(now,to,1,-w[i],0,w[i]);
        }
        printf("%d\n",EK());
     //   cout<<EK()<<endl;
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/zz_1215/article/details/7270724