poj 1821 Fence

时间：2010-10-20 来源：niuniu2006t

重回poj，昨晚搞的很郁闷，哎... 思路有点问题，发现有篇讲的很好，就不浪费口舌了，直接拷过来吧。－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

Fence

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 1347		Accepted: 367

Description

A team of k (1 <= K <= 100) workers should paint a fence which contains N (1 <= N <= 16 000) planks numbered from 1 to N from left to right. Each worker i (1 <= i <= K) should sit in front of the plank Si and he may paint only a compact interval (this means that the planks from the interval should be consecutive). This interval should contain the Si plank. Also a worker should not paint more than Li planks and for each painted plank he should receive Pi $ (1 <= Pi <= 10 000). A plank should be painted by no more than one worker. All the numbers Si should be distinct.

Being the team's leader you want to determine for each worker the interval that he should paint, knowing that the total income should be maximal. The total income represents the sum of the workers personal income.

Write a program that determines the total maximal income obtained by the K workers.

Input

The input contains:
Input

N K
L1 P1 S1
L2 P2 S2
...
LK PK SK

Semnification

N -the number of the planks; K ? the number of the workers
Li -the maximal number of planks that can be painted by worker i
Pi -the sum received by worker i for a painted plank
Si -the plank in front of which sits the worker i

Output

The output contains a single integer, the total maximal income.

Sample Input

Sample Output

Hint

Explanation of the sample:

the worker 1 paints the interval [1, 2];

the worker 2 paints the interval [3, 4];

the worker 3 paints the interval [5, 7];

the worker 4 does not paint any plank
题目意思就是说给你一段墙，有K个粉刷工，每个粉刷工站在一个位置，且每个粉刷工只能刷L连续长度的墙，且要包括他所在的位置，而且每个粉刷工刷一个单位的墙的价格也不一样，问怎么刷能达到最大价钱

先以P为关键字对工人进行排序，使这个顺序作为动态规划的阶段。

定义F[I]代表粉刷前I个栅栏最大价值，有如下状态转移方程：
F[I]:=Max{F[J]+Len*Cost}
显然，这个方程的复杂度是O（K*N*N）的，我们需要对其进行优化。

顺序枚举工人I，递减的枚举右边界J，然后定义一个变量K，初始时K=P[I]，代表第I个工人粉刷的左边界。
显然F[J]:=Max{F[K-1]+（J-K+1）*Cost[I]}
现在的关键就在于维护这个K。

当递减循环到J'的时，设T=J'-Len[I]+1，当（(K-1）-T+1）*Cost[I]>F[K-1]-F[T-1]时，K:=T，否则K不变。（画画图就明白了），这里表示对于下面一个右边界是否需要移动其左边界。
所以，维护K只需要O（1）的时间，整个DP复杂度就降到了O（N^2）。
代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
long N,K;
long f[16100];
struct Painter
{
       long length;
       long sit;
       long price;
       bool operator < (const struct Painter &a) const
       {
            return sit<a.sit;
       }
}p[120];
int main()
{
    long ibegin,iend,i,j,ans;
    while(EOF!=scanf("%ld%ld",&N,&K))
    {
       ans=0;
        memset(f,0,sizeof(f));
        for(i=1;i<=K;i++)
        scanf("%ld%ld%ld",&p[i].length,&p[i].price,&p[i].sit);
        sort(p+1,p+1+K);
        for(i=1;i<=K;i++)
        {
            ibegin=p[i].sit;
            for(iend=p[i].sit+p[i].length-1;iend>=p[i].sit;iend--)
            {
               if(iend<=N&&iend-p[i].length<=0) f[iend]=max(f[iend],iend*p[i].price);
               else if(iend<=N) f[iend]=max(f[iend],f[ibegin-1]+(iend-ibegin+1)*p[i].price);
               if(iend-p[i].length>0&&p[i].price*(p[i].length-(iend-ibegin))>f[ibegin-1]-f[ibegin-1-(p[i].length-(iend-ibegin))])
                     ibegin=iend-p[i].length;
            }
            for(iend=p[i].sit+p[i].length;iend<=N;iend++)
             f[iend]=max(f[iend],f[p[i].sit+p[i].length-1]);
        }
        ans=max(ans,f[N]);
        printf("%ld\n",ans);
    }
    return 0;
}