1. Description
有一個長度為 \(n\) 的序列，第 \(\forall i\in[1, n]\) 個位置上有權值 \(p_i\) 和能量值 \(a_i\)。
一開始你的能量值，疲勞值和貢獻值均為 \(0\)，可以從序列上的任意位置出發。
假定當前你位於第 \(x\) 個位置，擁有 \(t\) 的能量值，疲勞值為 \(k\)，那麼可以獲得 \(\lfloor \frac{p_x}{2^k} \rfloor\)
接着，你可以同時對自己的能量值和疲勞值分別進行操作： \(t\leftarrow a_x\)，\(k\leftarrow 0\)，也可以不操作。
然後，在 \(x + t \le n\) 並且 \(t \not= 0\) 的時候，你可以移動到 \(x + t\) 的位置，並使得疲勞值 \(k\leftarrow k + 1\)，也可以不移動，然後結束所有操作。
請求出從某個點出發的最大貢獻值之和。
2. Solution
應該用 dp 解題，但是如果你寫出一個暴力的 \(f_{i,t,k}\) 來表示在 \(i\) 這個位置，能量值為 \(t\)，疲勞值為 \(k\) 的最大收益，那麼就不好做了。所以我們考慮壓掉兩維狀態，套路的，我們定義 \(f_i\) 表示從 \(i\) 和 \(i\) 之前出發，強制在 \(i\)
那麼轉移顯然：\(f_i=\max_{a_j\mid (i-j)}(f_j+\sum_{k=0}^{\frac{i-j}{a_j}}\frac{p_{j+ka_j}}{2^k})\)，採用刷表法轉移，後面的 \(\sum_{k=0}^{\frac{i-j}{a_j}} \frac{p_j+ka_j}{2^k}\) 可以在轉移過程中一併處理出來，時間複雜度就是 \(O(\sum_{i=1}^n\frac{n-i}{a_i})\)。而看到 \(\frac{n-i}{a_i}\)
如果 \(\frac{n-i}{a_i}\le \sqrt n\) 的位置，我們可以直接暴力跑刷表法，時間複雜度為 \(O(n\sqrt n)\)，可以通過。
對於 \(\frac{n-i}{a_i}>\sqrt n\)，我們可以得到的只有 \(a_i< \sqrt n\)
根據上面的轉移式子，我們不難發現兩個性質：
- 當 \(j\) 可以轉移到 \(i\) 時必然滿足 \(a_j\mid i-j\)，也就是滿足 \(i\equiv j\pmod {a_j}\)。
- 由於每個位置的貢獻是 \(\lfloor \frac{p_x}{2^k}\rfloor\)，所以其實最多跳了 \(30\) 步之後，\(f_j+\sum_{k=0}^{\frac{i-j}{a_j}}\frac{p_{j+ka_j}}{2^k}\)
所以，我們對於 \(\frac{n-i}{a_i}>\sqrt n\) 的位置首先暴力轉移 \(30\) 步，同時計算出不再發生變化的 \(val=f_j+\sum_{k=0}^{\frac{i-j}{a_j}}\frac{p_{j+ka_j}}{2^k}\) ，然後然後將 \((j,val)\) 這一二元組儲存在第 \(31\)
然後在轉移過程中，我們維護一個最值數組 \(mx_{i,j}\) 表示在當前位置之前，下標模 \(i\) 等於 \(j\) 的所有位置中可以得到的 \(val\) 的最大值是多少，接着當我們遍歷到 \(x\) 這個位置的時候，遍歷 \(mx_{i,x\bmod i}\) 對 \(f_x\)
時間複雜度為 \(O(n\sqrt n)\)，當然，由於第二種轉移的常數比較大，所以可以適當的調大塊長來平衡時間複雜度。
3. Code
/*by qwer6*/
/*略去缺省源與快讀快寫*/
const int N=5e5+5,M=715;
int n;
ll ans;
int p[N],a[N];
ll f[N],mx[M][M];
struct Modify{
int x,y;
ll val;
};
vector<Modify>modify[N];
signed main(){
read(n);
for(int i=1;i<=n;i++)f[i]=read(p[i]),read(a[i]);
int B=1500,C=n/B+1;
for(int i=1;i<=n;i++){
for(auto tmp:modify[i])
tomax(mx[tmp.x][tmp.y],tmp.val);
for(int j=1;j<C;j++)
tomax(f[i],mx[j][i%j]);
tomax(ans,f[i]);
if((n-i)/a[i]<=B){
ll val=0,k=1;
for(int j=i+a[i];j<=n;j+=a[i],k++){
if(k<=30)val+=p[j]>>k;
tomax(f[j],f[i]+val);
}
}else{//現在這裏至少可以跳 30 次
ll val=0,j=i+a[i];
for(int k=1;k<=30;k++,j+=a[i]){
val+=p[j]>>k;
tomax(f[j],f[i]+val);
}
if(j<=n)
modify[j].push_back({a[i],i%a[i],f[i]+val});
}
}
write(ans);
}4.後記
—師兄你是喜歡小龍女麼？
—你們都叫她小龍女麼？
