不看题解我不会

题意:

有 k(k<=100) 个人粉刷 n 面连续的篱笆 (n<=16000)。第 i 人做在 Si 位置上，手有 Li 长，也只能刷 Li 面连续篱笆，并且必须刷第 Si 面。或者他可以一面也不刷。第 i 人每刷 1 面得 Pi 元。求最多得的钱。

思路:

如果我们用 f[i][j] 表示前 i 人刷前 j 面墙的最大收益，那么首先有:

1. 第 i 人不刷:f[i][j]=max(f[i][j],f[i-1][j]);

2. 第 i 人刷，但不刷第 j 面:f[i][j]=max(f[i][j],f[i][j-1]);

其次，有:

3. 第 i 人刷第 j 面，且是从第 k+1 面刷到 j 面:f[i][j]=max(f[i][j],f[i-1][k]+Pi*(j-k)); 其中 k+1<=j 且 k+Li>=i

所以我么可以在 O(n^2k) 时间内求出所有 f[i][j].

但是这样对于此题还是太慢了:

注意到：如果将第三个方程变形:f[i][j]=max(f[i][j],f[i-1][k]-Pik+Pij) 那么我们会发现: 只要我们知道了满足条件的 f[i-1][k] 最大为多少，就可以准确而快速求出 f[i][j]。如何这么办到呢？

方案一:

我们只需要将所有 f[i-1][k]-Pik 保存下来，将可选的部分取最大值就可以了。这时候我们可以利用单调队列。O(logn) 转移。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

typedef struct peop
{
    int s,p,l;
}people;

people po[101];
int f[101][16001];
int n,k;

struct Data  
{  
    int val,pos;  
    bool operator<(const Data &ne)const  
    {  
        if(val!=ne.val)  
            return val<ne.val;  
        else  
            return pos>ne.pos;  
    }  
    Data(){}  
    Data(int _val,int _pos){val=_val;pos=_pos;}  
}temp[16002];

bool cmp(people a,people b)
{
    return a.s<b.s;
}

void input()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++)scanf("%d%d%d",&po[i].l,&po[i].p,&po[i].s);
    sort(po+1,po+k+1,cmp);
}

pair<int,int> q[16001];

void work()
{
    for(int i=1;i<=k;i++)
    {
        priority_queue<Data> q;
        for(int j=max(0,po[i].s-po[i].l);j<po[i].s;j++)q.push(Data(f[i-1][j]-po[i].p*j,j));
        for(int j=1;j<=n;j++)
        {
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(j<po[i].s||j-po[i].l>=po[i].s)continue;
            while(!q.empty()&&q.top().pos+po[i].l<j)q.pop();
            if(!q.empty())f[i][j]=max(f[i][j],q.top().val+po[i].p*j);
        }
    }
    cout<<f[k][n]<<endl;
}

int main()
{
    input();
    work();
    return 0;
}

方法 2:

我们可以利用单调队列，维护数据位置的递增和值的递减。就可以 O(1) 转移。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

typedef struct peop
{
    int s,p,l;
}people;

people po[101];
int f[101][16001];
int n,k;

struct Data  
{  
    int val,pos;
    Data(){}  
    Data(int _val,int _pos){val=_val;pos=_pos;}  
}q[16002];

bool cmp(people a,people b)
{
    return a.s<b.s;
}

void input()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++)scanf("%d%d%d",&po[i].l,&po[i].p,&po[i].s);
    sort(po+1,po+k+1,cmp);
}

void work()
{
    int h,t;
    for(int i=1;i<=k;i++)
    {
        h=0,t=1;
        for(int j=max(0,po[i].s-po[i].l);j<po[i].s;j++)
        {
            int tmp=f[i-1][j]-po[i].p*j;
            while(h>=t&&q[h].val<tmp)h--;
            q[++h]=Data(tmp,j);
        }
        for(int j=1;j<=n;j++)
        {
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(j<po[i].s||j-po[i].l>=po[i].s)continue;
            while(h>=t&&q[t].pos+po[i].l<j)t++;
            if(h>=t)f[i][j]=max(f[i][j],q[t].val+po[i].p*j);
        }
    }
    printf("%d\n",f[k][n]);
}

int main()
{
    input();
    work();
    return 0;
}