题解：AT_abc417_d [ABC417D] Takahashi's Expectation

· · 题解

题目简述

给定一个正整数 n，及 3 个长度为 n 的数组 p_1,p_2,\dots,p_n、a_1,a_2,\dots,a_n、b_1,b_2,\dots,b_n，q 次询问，每次给定一个 x，对于每个 1\le i \le n，依次执行以下操作：

对于每个询问输出最终的 x。

思路

我们不难想到 DP，令 dp_{i,j} 为执行完 1 \sim i，当前数为 j，若执行完 i + 1 \sim n 后的答案。那么显然我们有如下转移。

每次查询 x，则答案为 dp_{0,x}。不过注意到 j 最大有 10^9，显然不可行。

以下我们令 m = \max_{i=1}^{n} p_i \le 500。

可以发现，如果 x > m 那么一定是有一段 1 \sim n 的前缀，在此前缀中一定是一直减 b_i，直到 x \le m 才有可能不会再减，这样我们可以把 x \le 10^9 的问题转换为 x \le m 的问题。（找到这个临界点可以使用二分）

那么我们再来思考 x \le m，可以观察到 x 在依次执行操作期间上限至多 \max_{i=1}^{n} p_i + a_i，显然在执行完 1 \sim i - 1 后要在第 i 次增加，x 至多 p_i，所以执行完 1 \sim i 后至多 p_i+a_i，所以总上限为 \max_{i=1}^{n} p_i + a_i。

我们只用对 0 \le j \le \max_{i=1}^{n} p_i + a_i \le 1000 范围内的 j DP 即可。

复杂度分析

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int MAXN = 1e4 + 5, MAXV = 1e3 + 1;
//这里我索性将上限提为 1000

int n, q, p[MAXN], a[MAXN], b[MAXN], dp[MAXN][MAXV], sum[MAXN];

int Calc(int x){
  if(x < MAXV) return dp[0][x];
  int pos = lower_bound(sum + 1, sum + 1 + n, x - MAXV + 1) - sum;//二分找到临界点
  return pos <= n ? dp[pos][max(0, x - sum[pos])] : x - sum[n];
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> p[i] >> a[i] >> b[i];
    sum[i] = sum[i - 1] + b[i];//b 的前缀和
  }
  for(int i = 0; i < MAXV; i++) dp[n][i] = i;//初始化
  for(int i = n - 1; i >= 0; i--){//DP
    for(int j = 0; j < MAXV; j++){
      dp[i][j] = p[i + 1] >= j ? dp[i + 1][j + a[i + 1]] : dp[i + 1][max(0, j - b[i + 1])];
    }
  }
  cin >> q;
  for(int x; q; q--){
    cin >> x;
    cout << Calc(x) << '\n';
  }
  return 0;
}