专栏文章

题解：AT_abc417_d [ABC417D] Takahashi's Expectation

EExscallop64_
AT_abc417_d题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miojzwxp
此快照首次捕获于
2025/12/02 20:27
3 个月前
此快照最后确认于
2025/12/02 20:27
3 个月前
查看原文

题目简述

给定一个正整数 nn，及 33 个长度为 nn 的数组 p1,p2,…,pnp_1,p_2,\dots,p_n、a1,a2,…,ana_1,a_2,\dots,a_n、b1,b2,…,bnb_1,b_2,\dots,b_n，qq 次询问，每次给定一个 xx，对于每个 1≤i≤n1\le i \le n，依次执行以下操作：
  • 若 pi≥xp_i \ge x，则 xx 变为 x+aix + a_i；否则，xx 变为 max⁡(x−bi,0)\max(x - b_i,0)。
对于每个询问输出最终的 xx。

思路

我们不难想到 DP，令 dpi,jdp_{i,j} 为执行完 1∼i1 \sim i，当前数为 jj，若执行完 i+1∼ni + 1 \sim n 后的答案。那么显然我们有如下转移。
  • 若 pi+1≥jp_{i + 1} \ge j，则 dpi,j=dpi+1,j+ai+1dp_{i,j} = dp_{i+1,j+a_{i+1}}。
  • 若 pi+1<jp_{i+1} < j，则 dpi,j=dpi+1,max⁡(0,j−bi+1)dp_{i,j} = dp_{i+1,\max(0,j-b_{i+1})}。
每次查询 xx，则答案为 dp0,xdp_{0,x}。不过注意到 jj 最大有 10910^9，显然不可行。
以下我们令 m=max⁡i=1npi≤500m = \max_{i=1}^{n} p_i \le 500。
可以发现，如果 x>mx > m 那么一定是有一段 1∼n1 \sim n 的前缀，在此前缀中一定是一直减 bib_i，直到 x≤mx \le m 才有可能不会再减，这样我们可以把 x≤109x \le 10^9 的问题转换为 x≤mx \le m 的问题。（找到这个临界点可以使用二分）
那么我们再来思考 x≤mx \le m，可以观察到 xx 在依次执行操作期间上限至多 max⁡i=1npi+ai\max_{i=1}^{n} p_i + a_i，显然在执行完 1∼i−11 \sim i - 1 后要在第 ii 次增加，xx 至多 pip_i，所以执行完 1∼i1 \sim i 后至多 pi+aip_i+a_i，所以总上限为 max⁡i=1npi+ai\max_{i=1}^{n} p_i + a_i。
我们只用对 0≤j≤max⁡i=1npi+ai≤10000 \le j \le \max_{i=1}^{n} p_i + a_i \le 1000 范围内的 jj DP 即可。

复杂度分析

  • 时间复杂度：O(n(max⁡i=1npi+ai)+qlog⁡n)O(n(\max_{i=1}^{n} p_i+a_i) + q \log n)。（为什么带个 log⁡\log，因为需要二分查找）
  • 空间复杂度：O(n(max⁡i=1npi+ai))O(n(\max_{i=1}^{n} p_i+a_i))。
CPP
#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;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...