http://codeforces.com/contest/319/problem/B

 

题目大意：

有删除操作，每次都删除数组右边比自己小的、且紧挨着自己的数字。问最小需要删除几次。

思路：

我们定义dp[i]表示删除右边的所有元素需要几次，然后用deque或者stack维护（最小的在顶端），从右边开始逆推（这样就保证了stack或deque中的数字在序列中的大小），然后在pop的同时要注意比较t和dp[j]的大小就可以了。

#include
      
       using namespace std;const int maxn = 100000 + 5;int a[maxn];int dp[maxn];int n;void solve(){    memset(dp, 0, sizeof(dp));    stack 
       
        
          > s;    s.push(make_pair(n - 1, a[n - 1]));    for (int i = n - 2; i >= 0; i--){        int t = 0;        pair 
         
           p;        while (!s.empty() && s.top().second < a[i]){            p = s.top();            t = max(dp[p.first], t + 1);            s.pop();        }        s.push(make_pair(i, a[i]));        dp[i] = t;    }    int cnt = 0;    for (int i = 0; i < n; i++) cnt = max(cnt, dp[i]);    cout << cnt << endl;}int main(){    while (scanf("%d", &n) == 1){        for (int i = 0; i < n; i++) scanf("%d", a + i);        solve();    }    return 0;}