NOIP模拟赛队爷的 Au Plan

队爷的 Au Plan

问题描述

队爷为了变得越来越神，他给自己制定了 n 个任务，编号为 1，2，…,n。队爷在完成这些任务之前有一个初始兴奋值 m，每个任务都有一个难度值 hard[i],且对于任何 i>j，有 hard[i]>hard[j]，队爷
完成第 i 个任务，兴奋值至少会减少 hard[i]，第 i 任务完成之后，队爷会受到鼓舞，兴奋值又会增加 s[i]，每个任务只完成一次。队爷可以一次完成所有剩余的难度值不超过现有兴奋度的任务，这样只会消
耗那个最大的难度值。现在队爷想知道完成这 n 个任务之后，他的最大兴奋值为多少。

输入文件

第一行 2 个整数 n，m，如题意。
第二行 n 个整数，第 i 个为 hard[i]。
第三行 n 个整数，第 i 个为 s[i]。

输出文件

一个整数，为完成这 n 个任务之后的最大兴奋值。

输入样例

5 5
2 4 5 7 9
4 4 3 6 5

输出样例

样例解释

第一次完成前 2 个任务，兴奋值为 9；
第二次完成后 3 个任务，兴奋值为 14。

数据规模与约定

对于 30%的数据，1<=n<=2000
对于另外 20%的数据，所有的 s[i]之和小于 200000；
对于 100%的数据，1<=n<=200000，数据保证所有任务都能完成。

分析

一道动态规划的题目，转移的时候寻找单调性，单调队列维护可以达到O(n)。

附上题解

30分算法：

考虑动态规划，f[i]表示完成前i个任务的最大兴奋值，sum[i]表示前i个任务获得兴奋值的和，则i状态要从前面一个能完成i任务的状态转移来，易得f[i]=max(f[j]-hard[i]+sum[i]-sum[j])，0<=j<i且f[j]>hard[i]，对于每一个i暴力枚举0到i-1中的状态即可，时间复杂度为O(n^2),

50分算法：

整理状态转移方程得f[i]=max(f[j] -sum[j])-hard[i]+sum[i]，对于s[i]之和小于200000的数据，以f[i]为关键字建立线段树，每个节点记录区间内f[i]-sum[i]的最大值，则对于每个i只要查询 [hard[i],sum[n]]内f[j]-sum[j]的最大值即可，时间复杂度O(nlog sum[n])，结合30分算法之后可以得到50分。

100分算法：

对于i状态，考虑j，k两个决策，j<k<i且f[j]>hard[i]&&f[k]>hard[i]。若j，k不为前面同一个决策转移得到，则k的决策层数显然会更大，即额外消耗更多，所以j优于k；若j，k为前面同一个决策l转移得到：
f[j]=f[l]-sum[l]+sum[j]-hard[j],f[k]=f[l]-sum[l]+sum[k]-hard[k],
f[j]-f[k]=sum[j]-sum[k]+hard[k]-hard[j],
f[j]-sum[j]-(f[k]-sum[k])=hard[k]-hard[j],
即f[j]-sum[j]> f[k]-sum[k],所以j决策优于k决策，
所以对于每一个状态i，最小的能够转移到i的决策总是最优的，这样只需要用单调队列维护决策即可（其实一个指针就OK了），时间复杂度为O(n)。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+5;
inline int read(){
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m;
int h[N],s[N],f[N];
int main(){
    n=read();m=read(); f[0]=m;
    for(int i=1;i<=n;++i) h[i]=read();
    for(int i=1;i<=n;++i) s[i]=s[i-1]+read();
    for(int i=1,j=0;i<=n;++i){
        while(f[j]<h[i]) ++j;
        f[i]=f[j]+s[i]-s[j]-h[i];
    }
    printf("%d
",f[n]);
    return 0;
}

NOIP模拟赛 队爷的 Au Plan