P4945 最后的战役 题解

· · 题解

update: 修正代码错误

本题有两种不同做法，复杂度也不同。

这道题明显在某秒取第 1 种还是第 2 种收集对其他秒没有影响，所以如果在某一秒要收集，那直接取能量最高的一种收集就可以。

操作 1 可以先把 k,p 离线记录下来，用离散化或者 map 计算到这一层某种类型的收集量。操作 2 很好处理。这样我们就可以设 y[i] 为第 i 秒收集时获得的能量。

这样我们把题目简化到只需处理第 3 种操作，对于第三种操作，有两种解法。

方案一：DP

很容易想到，设 f[i][j]为第 i 秒用了 j 加倍收集的最大能量值。转移方程就是。

f[i][j]=\max(f[i-1][j]+y[i],f[i-2][j-1]+y[i]*2)

前一个是正常收集，后一个是翻倍。

时间复杂度和空间复杂度都是 O(nm) ，这道题里如果极限数据可以爆 int，开 longlong 就快要用完空间了，那有什么其他方法吗？

方案二：转化+贪心

这道题的题解中，有一个人睿智的提出了一种贪心方法：

如果一次加倍都不用，答案明显是 \sum_{i=1}^{n}y[i] 所有数的和。

而在 a 位置用加倍相当于损失了 y[a] 但增加了 y[a+1]。

所以我们可以设 t[i] 为 y[i+1]-y[i] ，也就是 i 位置用翻倍的贡献，但因为不能连用翻倍魔法，问题转化为：

n-1 个数 t[i]，最多取 m 个不相邻的数，求所取数最大值。

很可惜的是这位同学的贪心方法错误，这道题现在类似于 P1484 正确方法是把这些数丢进优先队列，取出一个数时，将 两边的数-这个数 丢回队列。这样取出这个数等于放弃原来的数而取相邻的两个。详细解法见 P1484 的题解区 链接 。

时间复杂度 O((n+m)log\ n)。空间则只有 O(n) 。

代码

DP:

#include<iostream>
#include<map>
using namespace std;

long long f[50002][501];
long long y[50002];
long long a1[50002];
long long a2[50002];
map<int,long long> u;
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a1[i]>>a2[i];
        y[i]=max(y[i-1],a2[i]);
    }   
    for(int i=1;i<=n;i++){
        int k;cin>>k;
        u[a1[i]]+=a2[i];
        y[i]=max(y[i],u[k]);
    }
    f[1][0]=y[1];
    for(int i=2;i<=n;i++){
        f[i][0]=f[i-1][0]+y[i];
        for(int j=1;j<=m;j++){
            f[i][j]=max(f[i-1][j]+y[i],f[i-2][j-1]+y[i]*2);
        }
    }
    long long ans=0;
    for(int i=0;i<=m;i++){
        ans=max(ans,f[n][i]);//不一定把m次用完
    }
    cout<<ans;
    return 0;
}

转化贪心：

#include<iostream>
#include<map>
#include<queue>
using namespace std;
struct dui{
    int s,t;
};
bool operator < (dui a,dui b){
    return a.s<b.s;
}
priority_queue<dui> d;
long long y[50002];
long long a1[50002];
long long a2[50002];
long long t[50002];
bool q[50002];
int fr[50002],be[50002],no[50002];
map<int,long long> u;
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a1[i]>>a2[i];
        y[i]=max(y[i-1],a2[i]);
    }   
    for(int i=1;i<=n;i++){
        int k;cin>>k;
        u[a1[i]]+=a2[i];
        y[i]=max(y[i],u[k]);
    }
    long long ans=y[1];
    for(int i=1;i<n;i++){
        ans+=y[i+1];//累加本来就有的
        t[i]=y[i+1]-y[i];
        fr[i]=i-1;be[i]=i+1;no[i]=t[i];
        d.push(dui{t[i],i});
    }
    no[0]=no[n]=0;be[n]=n;
    for(int i=0;i<m;i++){
        dui o=d.top();d.pop();int h=o.t;
        if(o.s<=0)break;//如果收益是负数自然就不需要用了
        if(q[h]==1){
            m++;continue;
        }
        q[fr[h]]=1;q[be[h]]=1;
        no[h]=no[fr[h]]+no[be[h]]-o.s;
        d.push(dui{no[h],h});
        fr[h]=fr[fr[h]];be[h]=be[be[h]];
        ans+=o.s;
    }
    cout<<ans;
    return 0;
}