题解：AT_abc417_d [ABC417D] Takahashi's Expectation

· · 题解

感觉正着推 DP 好难...何不尝试一下记忆化搜索呢？

题目大意

Takahashi 按顺序收到了 n 个礼物。每个礼物 i 具有三个参数：P_i、A_i、B_i。Takahashi 初始具有一个心情值 X，当收到礼物时有 X>P_i 则其心情下降 B_i，否则其心情会上升 A_i。Takahashi的心情永不会低于 0。

给出 Q 个询问，要求回答若 Takahashi 的初始心情值为 X_i，其收完所有礼物后的心情值会是多少。

解法

注意到题目给出的 P_i、A_i、B_i 的范围不大（\le500），同时由于这是一个“负反馈系统”，所以如果值在 1000 以内的话它仍然会被约束在 1000 以内，所以搜索时只需要处理在 1000 以内的部分即可。

若初始的 X 高于 1000 ，根据题目给出的提示，X 将在一段时间内持续下降，因此可以通过前缀和加二分预处理出“高于 1000 而单调下降”的这一部分，余下的再进行搜索。

这道题有一个性质，就是状态之间的转移是一一对应的，所以对于记忆化搜索非常之友好（不容易写炸...）。

AC Code

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

const int N=1e4+9,M=1001;
int n,q,p[N],a[N],b[N],pb[N],dp[N][M];
bitset<M> vis[N];

int dfs(int i,int j){
    if(vis[i][j]) return dp[i][j]; //若搜过则返回
    vis[i][j].flip();
    int nv=max(j+(p[i]>=j?a[i]:-b[i]),0ll); //判断增加心情还是减少心情
    if(i==n) return dp[i][j]=nv; //搜到尾部，返回
    else return dp[i][j]=dfs(i+1,nv);
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>p[i]>>a[i]>>b[i];
    partial_sum(b+1,b+1+n,pb+1); //处理前缀和
    cin>>q;
    for(int i=1,x;i<=q;i++){
        cin>>x;
        auto it=lower_bound(pb+1,pb+1+n,x-1000); //削除x>1000的部分
        if(it>=pb+n) cout<<x-pb[n]; //一点心情都没有增加
        else if(it==pb+1) cout<<dfs(1,x); //已经在域中
        else cout<<dfs(it-pb+1,x-*it); //其余情况，从中间开始
        cout<<'\n';
    }
    return 0;
}

时间复杂度分析

时空均为 O(n\times D)，其中 D 为进行转移的值域。