题解：AT_abc417_d [ABC417D] Takahashi's Expectation

· · 题解

我不会告诉你这道题比第五题难。

首先，暴力模拟肯定不行，因为时间复杂度会达到 \mathcal O(nq)，必然超时。而我们发现 p、a、b 数组最大都只有五百，而 n 也只有一万，这启示我们用 \mathcal O(np) 的算法。

再观察一下，我们会发现如果第 i 次之前的心情小于 p_i，那么他之后的心情永远不会超过一千，因为如果他的心情超过 p_i （之后我们暂时默认 p_i 都为五百），那他的心情一定会疯狂下降，直到跌入五百大关。之后心情会上升，但最大情况下，此时心情为五百，a_i 也为五百，那它的心情达到一千，之后必然会掉，因为这必然会超过 p_{i+1}。接下来回到全局，如果高桥的初始心情超过 p_1，那他的心情就会一直掉，直到掉进五百大关，再遵循情况一，心情在零到一千间上下起伏。所以我们把情况分成两部分：一直掉的阶段，上下起伏的阶段。

上下起伏的阶段容易实现。我们设 dp_{i_j} 为从第 i 个礼物开始拿，一直拿到最后一个。而拿之前的心情为 j 时的最终心情。递推式极其简单：当 j \le p_i 时，dp_{i_j}=dp_{i+1_{j+a_i}}，因为他拿了这个后，相当于从第 i+1 个礼物开始拿，此时心情为 j+a_i 的最终心情；否则 j>p_i 时，dp_{i_j}=dp_{i+1_{\max(0,j-b_i)}}，因为他拿了这个后，相当于从第 i+1 个礼物开始拿，此时心情为 \max(0,j-b_i) 的最终心情（因为心情是要大于等于零的）。

至于初始状态，把所有 dp_{n+1_i} 的位置初始化成 i 即可。

接下来我们看一直下降的阶段。在此之前，我们设 s_i=\sum_1^i b_i，也就是前缀和。而我们要找的就是第一个 x-s_{i-1} \le p_i 的位置。因为从 i 点开始（包括这个点），它就进入第二阶段了，结果就是刚才预处理出的结果了。不过显然暴力不行；而看到这种，你可能第一时间想到二分，然而很遗憾，这玩意不满足单调性。不过好在 s_i 不会太大，我们可以换一种思路。

首先，我们设 f_i 为满足 s_{j-1}+p_j=i 中最小的 j 的值。这很容易预处理；然后我们对 f_i 从后往前做一次后缀最小值，然后 f_i 的值就变成了 s_{j-1}+p_j \ge i 中最小的 j 的值。而在查询的循环中原先找到的那个 i，就可以替换成 f_x 了，时间复杂度一下子降到了 \mathcal O(1)。

还有，如果 x 减去前 n-1 个 b_i 还大于 p_n，就意味着没有经历第二阶段，要特判输出。

代码：

#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int N=1e4+10,M=1000; 
//dp_i_j 从第i个物品开始拿，此时心情为j的最终值 
int p[N],a[N],b[N],s[N],dp[N][M+10],f[N*505+10]; //那些数组
signed main(){
    ios::sync_with_stdio(0); //快读
    cin.tie(0),cout.tie(0);
    int n,q;
    cin>>n;
    for(int i=0;i<=n*505+1;i++) f[i]=1e18; //初始化成最大值
    for(int i=1;i<=n;i++){
        cin>>p[i]>>a[i]>>b[i];
        s[i]=s[i-1]+b[i];
        f[s[i-1]+p[i]]=min(f[s[i-1]+p[i]],i); //初始化f数组
    }
    for(int i=n*505;i>=0;i--) f[i]=min(f[i],f[i+1]);  //后缀最小值
    for(int j=1;j<=M;j++) dp[n+1][j]=j; //dp预处理
    for(int i=n;i>=1;i--){
        for(int j=0;j<=M;j++){
            if(j<=p[i]) dp[i][j]=dp[i+1][j+a[i]];
            else dp[i][j]=dp[i+1][max(0ll,j-b[i])]; //两种情况
        }
    }
    cin>>q;
    while(q--){
        int x;
        cin>>x;
        if(x-s[n-1]>p[n]) cout<<max(0ll,x-s[n])<<endl; //特判
        else cout<<dp[f[x]][max(0ll,x-s[f[x]-1])]<<endl; //输出答案
    }
    //n<=p_x+s_x
    return 0;
}

时间复杂度可以认为是预处理 \mathcal O(n) 乘一个一千左右的大常数；查询 \mathcal O(q)。反正能过。

最后，再次无耻地求过。