专栏文章
题解：AT_abc417_d Takahashi's Expectation
AT_abc417_d题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @miok24fh
- 此快照首次捕获于
- 2025/12/02 20:29 3 个月前
- 此快照最后确认于
- 2025/12/02 20:29 3 个月前
观察到 的值域很小，考虑冲这里。
由于 ，可以发现当当前的心情值（下面称为 ）大于 时， 也一定大于当前的 ，也就是说现在的操作是 。
观察到题目给出 ，看着非常恐怖。但根据刚才的分析，发现在 时，不需要管 ，只需要无脑减 即可，直到 。
可以通过简单的二分加前缀和快速求出不断减 这一步骤结束后的 以及这一步在第几次操作前结束。那么这一步以后该怎么办？
定义 dp 数组 ，表示当执行第 步操作之前的 时，最后得到的心情值（这里最后指所有操作结束以后）。状态转移方程为：
F_{i + 1, j + A_i} & j \leq P_i\\
F_{i + 1, \max(0, j - B_i)} & j > P_i
\end{cases}$$
dp 的初始条件为：
$$F_{n, j} = \begin{cases}
j + A_n & j \leq P_n \\
\max(0, j - B_n) & j > P_n
\end{cases}$$
然后上面的问题就只需要 $O(1)$ 调用 $F$ 即可解决，详见代码。
```cpp
#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;
}
```相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...