[POI 21 Stage 2] Little Bird

作法：

這題是單調隊列優化DP。當我們在算 dp[ i ] 的時候，會需要考慮到 dp[ i - k ] ~ dp[ i - 1 ] ，但如果這裡面存在 x , y 滿足 x < y 且 dp[ x ] > dp[ y ] ，那麼 x 就廢掉了，因為這裡的 DP 有個重要的性質，就是每次的轉移只會等於上一個的值或是上一個的值+1，所以在怎麼樣用 dp[ y ] 轉移 dp[ i ] 時大不了值多 1 而已，dp[ x ] 永遠不會比 dp[ y ] 好。所以只要維護一個 deque ，裡面保持 dp 值是遞增的，如果 dp 值一樣的話，就要把點的高度考慮進來了。因為越高的點在轉移時可以越有機會不用讓 dp 值增加，所以當 x 和 y 的 dp 值一樣 ( x < y )，且 a[ y ] > a[ x ] 時， x 就廢掉了，把他從 deque 裡 pop 掉。最後記得每次要從 deque 後面把過期的東西 pop 掉。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10 ;
 
int n,k ;
int a[maxn],dp[maxn] ;
deque<int> dq ;
 
main()
{
     scanf("%d",&n) ;
     for(int i=1;i<=n;i++) scanf("%d",&a[i]) ;
     int Q ; scanf("%d",&Q) ;
     while(Q--)
     {
          scanf("%d",&k) ;
          dq.clear() ;
          dp[1]=0 ; dq.push_front(1) ;
          for(int i=2;i<=n;i++)
          {
               while(dq.back()+k < i) dq.pop_back() ;
               dp[i]= a[dq.back()]>a[i] ? dp[dq.back()] : dp[dq.back()]+1 ;
               while(!dq.empty() && dp[dq.front()]>dp[i]) dq.pop_front() ;
               while(!dq.empty() && dp[dq.front()]==dp[i] && a[i]>a[dq.front()])
                    dq.pop_front() ;
               dq.push_front(i) ;
          }
          printf("%d\n",dp[n]) ;
     }
}