洛谷題目頁面傳送門 & AtCoder題目頁面傳送門
有\(1\)根數軸，Shik初始在位置\(0\)，數軸上有\(n\)只小熊，第\(i\)只在位置\(a_i\)，Shik每秒可以向左移動\(1\)個單位長度、原地不動或向右移動\(1\)個單位長度，Shik第\(1\)次到某個小熊的位置\(s\)秒后，小熊會在原地生產\(1\)個金幣，Shik必須再次到達此小熊的位置才能收集金幣，求Shik收集完所有金幣后到達位置\(m\)所花的最小秒數，
\(n\in\left[1,10^5\right],a_i\in(0,m),a_i<a_{i+1}\)，
考慮最優情況下，Shik的路線會是怎樣的，如果Shik經過了一些小熊，回頭收集了這些小熊中后面一部分的金幣，然后繼續往終點走，留下前面一部分金幣等到以后再收，這樣肯定不是最優的（感性理解），可以推出若一個小熊的金幣被收了，那么它前面的所有小熊的金幣都被收了，即被收了金幣的小熊序列是所有小熊序列的一個前綴，考慮將某時刻的前綴分成若干個區間，每個區間內的小熊都是在一次回頭中被收了金幣的，于是我們就可以DP了，
設\(dp_i\)表示Shik收完了前\(i\)個小熊的金幣并回到了位置\(a_i\)所花的最小秒數，不妨設\(a_0=0\)為起點，那么顯然邊界是\(dp_0=0\)，目標是\(dp_n+m-a_n\)，轉移的話，列舉當前被收了金幣的小熊前綴被劃分的最后一個區間的左端點的前一個小熊\(j\)，即最后一次回頭之前\([1,j]\)已經被收了，那么最后一次回頭收的是\([j+1,i]\)，顯然，路線是這樣的：先將前\(j\)個小熊的金幣收完，回到位置\(a_j\)，然后\(a_j\to a_i\)經過\([j+1,i]\)使它們生產金幣，然后\(a_i\to a_{j+1}\)回頭到第\(j+1\)個小熊，等待若干秒直到第\(j+1\)個小熊生產金幣，然后\(a_{j+1}\to a_i\)依次收完\([j+1,i]\)的金幣并回到位置\(a_i\)，那么狀態轉移方程就很好列了：
\[dp_i=\min_{j=0}^{i-1}\{dp_j+(a_i-a_j)+(a_i-a_{j+1})+\max\left(0,s-2(a_i-a_{j+1})\right)+(a_i-a_{j+1})\} \]
即
\[dp_i=\min_{j=0}^{i-1}\{dp_j+3a_i-a_j-2a_{j+1}+\max\left(0,s-2a_i+2a_{j+1}\right)\} \]
暴力轉移顯然是\(\mathrm O\!\left(n^2\right)\)的，于是考慮優化，注意到方程里有個\(\max\)很不好處理，于是分類討論，分成\(s-2a_i+2a_{j+1}\ge0\)和\(s-2a_i+2a_{j+1}<0\)這\(2\)種，此時方程變為了：（化簡后）
\[dp_i=\min\!\left(\min_{j\in[0,i),s-2a_i+2a_{j+1}\ge0}\{dp_j+a_i-a_j+s\},\min_{j\in[0,i),s-2a_i+2a_{j+1}<0}\{dp_j+3a_i-a_j-2a_{j+1}\}\right) \]
將關于決策變數\(j\)的放到一起，關于狀態變數\(i\)的和常量放到一起，得
\[dp_i=\min\!\left(\min_{j\in[0,i),2a_{j+1}\ge 2a_i-s}\{(dp_j-a_j)+(a_i+s)\},\min_{j\in[0,i),2a_{j+1}<2a_i-s}\{(dp_j-a_j-2a_{j+1})+3a_i\}\right) \]
\(2\)個\(\min\)的條件里的\(2a_{j+1}\)顯然有單調性，所以\(2\)個\(\min\)取的\(j\)都構成區間，特殊地，對于第\(2\)個\(\min\)，是前綴，即左端點為\(0\)的區間，又因為\(2a_i-s\)也有單調性，所以第\(1\)個\(\min\)的區間左端點單調遞增，對于每個\(i\)，這個左端點可以two-pointers求出，于是對于第\(1\)個\(\min\)維護單調佇列，對于第\(2\)個\(\min\)維護前綴最小值，\(\mathrm O(n)\)，
下面貼代碼：
#include<bits/stdc++.h>
using namespace std;
#define int long long//防爆int
const int inf=0x3f3f3f3f3f3f3f3f;
const int N=100000;
int n/*小熊個數*/,m/*終點*/,s/*小熊被Shik碰到至生產金幣之間的秒數*/;
int a[N+1];//小熊的位置
int dp[N+1];//dp[i]表示Shik收完了前i個小熊的金幣并回到了位置a[i]所花的最小秒數
int q[N],head,tail;//對于第1個min維護的單調佇列
signed main(){
cin>>n>>m>>s;
for(int i=1;i<=n;i++)cin>>a[i];
q[tail++]=0;//i=1,j=0滿足2a[j+1]>=2a[i]-t，歸第1個min，于是壓入單調佇列
int now=-1/*第2個min取的j構成的區間（前綴）的右端點*/,mn=inf/*當前的前綴最小值*/;
for(int i=1;i<=n;i++){
while(now+1<i&&2*a[now+2]<2*a[i]-s)now++,mn=min(mn,dp[now]-a[now]-2*a[now+1]);//將now往后移
while(head<tail&&q[head]<=now)head++;//維護單調佇列，彈出過時元素
while(head<tail&&dp[q[tail-1]]-a[q[tail-1]]>=dp[i-1]-a[i-1])tail--;//維護單調佇列隊尾嚴格單調遞增性
q[tail++]=i-1;//將j=i-1入隊
dp[i]=min(dp[q[head]]-a[q[head]]+a[i]+s,mn+3*a[i]);//狀態轉移方程
}
cout<<dp[n]+m-a[n]<<"\n";//目標
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/67305.html
標籤：C++
上一篇：#《Essential C++》讀書筆記# 第四章 基于物件的編程風格
下一篇：圖論初步<蒟蒻專屬文章>