题目描述：
https://atcoder.jp/contests/abc417/tasks/abc417_d
题目分析：
首先观察数据范围，发现P[i],A[i],B[i]的范围很小，都在500以内，而X[i]却可达到10^9
这样，高桥的心情X[i]在前几轮会一直减小，直到500以内
因此，我们可以计算X[i]经过几轮会到500以内，而后进行DP
计算X[i]经过几轮会到500以内，可以提前预处理B数组的前缀和，二分查找，复杂度 O(n * logn)
定义f[maxn][maxk] （maxk=1000，X[]+A[]）
f[i][j]表示接到第i件礼物前心情为j的最终心情，从i=n+1倒推即可
总状态数 n * k，转移是 O(1)的，故复杂度 O(n * k)，可通过本题
#include <iostream>
#define int long long
using namespace std;
const int MAXN=1e4+7;
const int MAXX=1005;//初始心情降到500以下后的最大值
const int INF=1000;
int val[MAXN],a[MAXN],b[MAXN];
int f[MAXN][MAXX];//收到第i件礼物前心情为j的最终心情
int s[MAXN];
signed main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>val[i]>>a[i]>>b[i];s[i]=s[i-1]+b[i];//前缀和}for(int i=0;i<=INF;i++){f[n+1][i]=i;//初始化}for(int i=n;i>=1;i--){//倒推f数组for(int j=0;j<=INF;j++){if(val[i]>=j){//增加f[i][j]=f[i+1][j+a[i]];}else{//减少int p=max(0LL,j-b[i]);//别忘了判负f[i][j]=f[i+1][p];}}}int q;cin>>q;while(q--){int x;cin>>x;if(x<=INF){//本身就比500小cout<<f[1][x]<<endl;continue;}int ans=n+1;int l=1,r=n;//经过[l,r]轮后while(l<=r){//二分答案int mid=(l+r)/2;if(x-s[mid]<=INF){ans=mid;r=mid-1;}else{l=mid+1;}}if(ans==n+1){//到最后一轮还比500大cout<<x-s[n]<<endl;}else{cout<<f[ans+1][x-s[ans]]<<endl;//注意f[i][j]表示收到第i件礼物"前"}}
}
完结撒花！