題干：

Description

In the Byteotian Line Forest there are ? trees in a row. On top of the first one, there is a little bird who would like to fly over to the top of the last tree. Being in fact very little, the bird might lack the strength to fly there without any stop. If the bird is sitting on top of the tree no. ?, then in a single flight leg it can fly to any of the trees no.i+1,i+2…I+K, and then has to rest afterward.

Moreover, flying up is far harder to flying down. A flight leg is tiresome if it ends in a tree at least as high as the one where is started. Otherwise the flight leg is not tiresome.

The goal is to select the trees on which the little bird will land so that the overall flight is least tiresome, i.e., it has the minimum number of tiresome legs. We note that birds are social creatures, and our bird has a few bird-friends who would also like to get from the first tree to the last one. The stamina of all the birds varies, so the bird's friends may have different values of the parameter ?. Help all the birds, little and big!

Input

There is a single integer N(2<=N<=1 000 000) in the first line of the standard input: the number of trees in the Byteotian Line Forest. The second line of input holds ? integers D1,D2…Dn(1<=Di<=10^9) separated by single spaces: Di is the height of the i-th tree.

The third line of the input holds a single integer Q(1<=Q<=25): the number of birds whose flights need to be planned. The following Q lines describe these birds: in the i-th of these lines, there is an integer Ki(1<=Ki<=N-1) specifying the i-th bird's stamina. In other words, the maximum number of trees that the i-th bird can pass before it has to rest is Ki-1.

Output

Your program should print exactly Q lines to the standard output. In the I-th line, it should specify the minimum number of tiresome flight legs of the i-th bird.

Sample Input

9
4 6 3 6 3 7 2 6 5
2
2
5

Sample Output

2
1

Hint

Explanation: The first bird may stop at the trees no. 1, 3, 5, 7, 8, 9. Its tiresome flight legs will be the one from the 3-rd tree to the 5-th one and from the 7-th to the 8-th.

題目大意：

有一排n棵樹，第i棵樹的高度是Di。

MHY要從第一棵樹到第n棵樹去找他的妹子玩。

如果MHY在第i棵樹，那么他可以跳到第i+1,i+2,...,i+k棵樹。

如果MHY跳到一棵不矮于當(dāng)前樹的樹，那么他的勞累值會(huì)+1，否則不會(huì)。

為了有體力和妹子玩，MHY要最小化勞累值。

解題報(bào)告：

?dp[i]表示從第一棵樹到第i棵樹所需的最小疲勞值。dp[i] = min(dp[j] + (s[i] > s[j]))

單調(diào)隊(duì)列中的元素主要考慮它的時(shí)效性和價(jià)值，時(shí)效性用來刪除隊(duì)頭，價(jià)值和時(shí)效性綜合考慮刪除隊(duì)尾。

單調(diào)隊(duì)列中的時(shí)效性是越靠后（在隊(duì)列中）越好，那么隊(duì)列中元素的價(jià)值是：疲勞值和樹高的綜合考慮。

注意，如果對(duì)于兩個(gè)位置j1和j2，有f[j1]<f[j2]，則j1一定比j2更優(yōu)。因?yàn)榫退鉰1高度比較矮，到達(dá)i頂多再多消耗1個(gè)疲勞值，頂多和j2相等。如果不需要消耗疲勞值，比j2更優(yōu)。 如果f[j1]=f[j2]，則我們比較它們的高度D，高度高的更優(yōu)。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 1e6 + 5; const ll INF = 0x3f3f3f3f; ll a[MAX],dp[MAX]; int n,q,k; deque<ll> dq; int main() {cin>>n;for(int i = 1; i<=n; i++) scanf("%lld",a+i);cin>>q;while(q--) {scanf("%d",&k);while(dq.size()) dq.pop_back();dq.push_back(1);dp[1] = 0;for(int i = 2; i<=n; i++) {dp[i] = INF;while(!dq.empty() && dq.front() < i-k) dq.pop_front();dp[i] = dp[dq.front()] + (a[i] >= a[dq.front()]);//注意這兩句的順序！！ while(!dq.empty() && (dp[dq.back()] > dp[i] || (dp[dq.back()]==dp[i]&&a[dq.back()]<=a[i])))//加等號(hào)是為了節(jié)省時(shí)間吧？因?yàn)檫@樣dq里的元素就少了。 dq.pop_back();dq.push_back(i);}printf("%lld\n",dp[n]);}return 0 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【BZOJ 3831】【Poi2014】Little Bird（单调队列优化dp）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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