正題

題目鏈接:https://www.luogu.com.cn/problem/P6563

---

題目大意

長度為$n$的序列$a_i$，現(xiàn)在有一個隨機$[1,n]$的整數(shù)，每次你可以花費$a_i$詢問這個數(shù)字是否大于$i$，求猜出所有數(shù)至少要多少花費。

$T\le 500,\sum n\le 7000$

保證$a_i$單調(diào)不降

---

解題思路

考慮區(qū)間$dp$，設(shè)$f_{l,r}$表示猜出區(qū)間$[l,r]$的最小花費。

最基本的轉(zhuǎn)移就是
$$f_{l,r}=min\{max\{f_{l,k},f_{k+1,r}\}+a_k\}(k\in [l,r))$$

然后考慮如何優(yōu)化轉(zhuǎn)移。

因為里面有個$max$，我們可以對于一個$l,r$考慮找到一個最小的$z$滿足$f_{l,z}>f_{z+1,r}$那么$z$以后的都是用$f_{l,z}$，以前的都是用$f_{z+1,r}$。

這個在右端點固定左端點向左時$z$是不升的，所以不用二分帶$log$。

對于取$f_{l,k}+a_k$的那一部分，$a_k$和$f_{l,z}$都隨著$k$增大不降，所以直接取$f_{l,z}+a_z$。

對于$f_{k+1,r}+a_k$的那一部分，$k$的限制會不斷縮小，所以用一個單調(diào)隊列維護就可以了。

時間復(fù)雜度$O(\sum n^2)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=7200; int T,n,a[N]; long long f[N][N]; deque<int> q; long long calc(int k,int r){if(k<1)return 1e18;return f[r][k+1]+a[k]; } signed main() {scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=j)f[i][j]=1e18; for(int r=2;r<=n;r++){q.clear();q.push_back(r-1);for(int l=r-1,z=r-1;l>=1;l--){while(z>l&&f[z-1][l]>f[r][z])z--;while(!q.empty()&&q.front()>=z)q.pop_front();if(!q.empty())f[r][l]=calc(q.front(),r);f[r][l]=min(f[r][l],f[z][l]+a[z]);if(l==1)continue;while(!q.empty()&&calc(q.back(),r)>=calc(l-1,r))q.pop_back();q.push_back(l-1);}}printf("%lld\n",f[n][1]);} }

總結(jié)

以上是生活随笔為你收集整理的P6563-[SBCOI2020]一直在你身旁【dp,单调队列】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。