題目

這里寫鏈接內容

題解

注意：題目給出是按照時間給出的順序。

我們考慮第ii個人要上的樓高h[i]h[i]，排在第ii個人前面的，所有要人上的樓高度≤h[i]≤h[i]的人都可以被合并在與第ii個人一起被傳送上去。

所以我們只需要考慮h[i]h[i]單調遞減的序列就可以了，其它的人我們都可以刪掉不看，因為它已經被合并了。

例如：
一個hh序列為1 8 2 5 4 3 2可以被縮短為8 5 4 3 2。
其中1被合并給8，2被合并給5。

我們按照上述方法對序列進行精簡，精簡之后是一個按照所需要達到樓層h[i]h[i]嚴格遞減的序列，然后我們就可以進行動態規劃了。

然后我們考慮動態規劃。
定義狀態dp[i]dp[i]表示第ii個位置電梯啟動，并且前ii個人全部被傳送到對應樓層所需的最小時間。

轉移方程：
對于ii,我們遍歷j，0≤j<ij，0≤j<i
dp[i]=min(max(dp[j]+2?h[j+1],t[i]+2?h[j+1]))dp[i]=min(max(dp[j]+2?h[j+1],t[i]+2?h[j+1]))
1. 也就是說當dp[j]<=t[i]dp[j]<=t[i]的時候，我們把第j+1…ij+1…i里面的人全都合并到t[i]t[i]的時間點運送上去。(第一部分)
2. 當dp[j]>t[i]dp[j]>t[i]的時候，我們把j+1…ij+1…i里面的人全都合并到dp[j]dp[j]的時間點運送上去。(第二部分)

我們可以用一個小技巧來處理上面兩種情況。

• 由于dp[i]dp[i]是非遞減的，我們設置一個變量stst表示dp[st?1]dp[st?1]小于等于當前t[i]t[i]的最大stst，這樣的話我們可以一開始就把第一種部分處理完。因為h[st]h[st]是滿足1≤j<i，且dp[j]≤t[i]1≤j<i，且dp[j]≤t[i]最小的h[j]h[j]。就是初始化dp[i]=t[i]+2?h[st]dp[i]=t[i]+2?h[st]，這樣一來，接下來的dp方程就被簡化為dp[i]=min(dp[j]+2?h[j+1])，dp[j]>t[i]dp[i]=min(dp[j]+2?h[j+1])，dp[j]>t[i] 這個式子就很好解決了，我們使用一個優先隊列來維護dp[j]+2?h[j+1]dp[j]+2?h[j+1]。
• 那么怎么處理dp[j]>t[i]dp[j]>t[i]這個小條件呢？考慮到t[i]t[i]是單調遞增的，凡是出現過dp[j]≤t[i]dp[j]≤t[i]的點，那么對于的i≤ki≤k中必定有dp[j]≤t[i]≤t[k]dp[j]≤t[i]≤t[k]。因此在優先隊列里面遇到dp[j]≤t[i]dp[j]≤t[i]這樣的點，我們直接把它刪除掉就可以了。

這樣的時間復雜度是O(nlog(n))O(nlog(n))

代碼

#include <iostream> #include <cstdio> #include <queue> #include <vector> using namespace std; typedef long long ll; int n,tail; #define pr(x) cout<<#x<<":"<<x<<endl const int maxn = 2e5+7; ll ts[maxn],hs[maxn],dp[maxn]; typedef pair<ll,int> pii; int mian(){tail = 0;if(scanf("%d",&n) != 1) return 0;for(int i = 1;i <= n;++i){ll t,h;scanf("%lld%lld",&t,&h);while(tail && hs[tail-1] <= h) tail--;ts[tail] = t;hs[tail] = h;tail++;}priority_queue<pii,vector<pii>,greater<pii> > Q;int st = 0;for(int i = 0;i < tail;++i){while(st < i && dp[st] <= ts[i]) st++;dp[i] = ts[i] + 2*hs[st];//初始化，解決dp第一部分while(!Q.empty()){pii p = Q.top();if(p.first <= ts[i] + 2*hs[p.second+1])Q.pop(); //對應題解里面處理小條件的方法else{dp[i] = min(dp[i],p.first);//解決dp第二步部分break; }}Q.push(make_pair(dp[i]+2*hs[i+1],i));}cout<<dp[tail-1]<<endl;return 1; }int main(){while(mian()); }

總結

以上是生活随笔為你收集整理的codeforces gym-101741 Elevator 动态规划、单调队列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。