题解：AT_abc417_d Takahashi's Expectation

yszkddzyh · 2025-08-02 22:55:20 · 题解

观察到 P,A,B 的值域很小，考虑冲这里。

由于 P_i \leq 500，可以发现当当前的心情值（下面称为 T）大于 500 时，T 也一定大于当前的 P_i，也就是说现在的操作是 T \gets T - B_i。

观察到题目给出 X_i \leq 10^9，看着非常恐怖。但根据刚才的分析，发现在 T > 500 时，不需要管 P_i，只需要无脑减 B_i 即可，直到 T \leq 500。

可以通过简单的二分加前缀和快速求出不断减 B_i 这一步骤结束后的 T 以及这一步在第几次操作前结束。那么这一步以后该怎么办？

定义 dp 数组 F_{i, j}，表示当执行第 i 步操作之前的 T = j 时，最后得到的心情值（这里最后指所有操作结束以后）。状态转移方程为：

dp 的初始条件为：

然后上面的问题就只需要 O(1) 调用 F 即可解决，详见代码。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int M = 1e3 + 5;
const int N = 1e4 + 5;
int n, Q, p[N], a[N], b[N], to[N][M], s[N];
// to 数组即是上文提到的 F 数组，s 数组是 b 的前缀和

int main(){

    ios :: sync_with_stdio(false);
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> p[i] >> a[i] >> b[i], s[i] = s[i - 1] + b[i];
    for(int i = 0; i <= 1000; i++){
        if(i <= p[n]) to[n][i] = i + a[n];
        else to[n][i] = max(0, i - b[n]);
    }
    // dp 数组的第二维需要到 1000 而不是 500
    // 因为可能会有类似 P_i = A_i = T = 500 的情况，此时 T 就会变成 1000
    for(int i = n - 1; i >= 1; i--){
        for(int j = 0; j <= 1000; j++){
            if(j <= p[i]) to[i][j] = to[i + 1][j + a[i]];
            else to[i][j] = to[i + 1][max(0, j - b[i])];
        }
    }
    cin >> Q;
    int x;
    while(Q--){
        cin >> x;
        int l = 1, r = n, mid, ans = -1;
        // ans 记录什么时候 T 第一次减至 500 及以下
        while(l <= r){
            mid = ((r - l) >> 1) + l;
            if(x - s[mid] <= 500) ans = mid, r = mid - 1;
            else l = mid + 1;
        }
        if(ans == -1){
            // ans == -1 表示减到最后 T 仍然大于 500
            cout << x - s[n] << "\n";
            continue;
        }
        x = max(0, x - s[ans - 1]);
        cout << to[ans][x] << "\n";
    }

    return 0;
}