不看题解我不会

题意:

有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;
}

 


分享至ヾ(≧∇≦*)ゝ:
分类: 所有

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *