洛谷-P15614 Happy Travelling 题解

提供一种 \(O(n\sqrt n)\) 的做法。

考虑数据结构优化 DP。如果正序做，\(dp_i\) 为从 \(1\to i\) 的最大值，那么只能主动转移，转化成单点查和区间修。正难则反，设 \(dp_i\) 为从 \(i\to n\) 的最大值，被动转移，变成单点修和区间查。这显然更好做。

转移方程即为

\[dp_i=h_i+\max_{i

自然想到枚举 \(\left\lceil\frac{j-i}{K}\right\rceil\) 的值并分别查询对应的区间。用朴素的线段树维护是 \(O\left(\frac{n^2\log n}{K}\right)\) 的。我们尝试优化掉这只 \(\log\)，做到 \(O(1)\) 查询。注意到每次修改一定是最左边加一个数，因此 ST 表可以带修，从而做到 \(O\left(\frac{n^2}{K}\right)\)。

以上做法只能在 \(K\) 较大时通过，这启发我们根号分治，尝试找到 \(O(nK)\) 的算法并拼起来。

固定 \(i\)，\(\left\lceil\frac{j-i}{K}\right\rceil\) 是关于 \(j\) 的函数，图像是 \(n/K+O(1)\) 个长为 \(K\) 的台阶。这启发我们枚举 \(j\bmod K\) 的余数。在一种余数内部，只需要维护全局 \(-1\)、左侧添加和前缀 \(\max\) 三种操作，同样用 ST 表维护，具体方法参见代码。

Code

#include 
#define rep(i,a,b) for(int i(a);ib;--i)
#define rept(i,a,b) for(int i(a);i<=b;++i)
#define pert(i,a,b) for(int i(a);i>=b;--i)
#define int long long
using namespace std;
constexpr int N=5e5+5,S=1000,L=19,INF=9e18;
int h[N],t[N];
int a[L][N],dp[N];
int n,k,d;
namespace A{
    // a[i][j]：j,j+k,j+2*k,...,j+(2^i-1)*k中的最大值
    int shift[S];
    inline void upd(int i,int x){  // 左侧单点加
        a[0][i]=x;
        rept(j,1,__lg(n/k+1)){
            if(i+(k<n) break;
            a[j][i]=max(a[j-1][i],a[j-1][i+(k<<(j-1))]);
        }
    }
    inline int query(int l,int r){  // 查询l,l+k,...,（最大的<=r且与l模k同余的数）中的最大值
        int len=(r-l)/k+1,d=__lg(len);
        r=l+(len-1)*k;
        return max(a[d][l],a[d][r-(k<i+t[i]) continue;
                dp[i]=max(dp[i],query(l,i+t[i])+shift[j]);
            }
            dp[i]+=h[i];
            upd(i,dp[i]-shift[i%k]);
            shift[(i-1)%k]-=d;
        }
        cout<n) break;
            a[j][i]=max(a[j-1][i],a[j-1][i+(1<sync_with_stdio(0);
    cin>>n>>k>>d;
    rept(i,1,n) cin>>h[i];
    rept(i,1,n-1) cin>>t[i];
    if(k