DP CF 319 div1B

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

题目大意：

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

思路：

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

#include<bits/stdc++.h>

using namespace std;

const int maxn = 100000 + 5;
int a[maxn];
int dp[maxn];
int n;

void solve(){
    memset(dp, 0, sizeof(dp));
    stack <pair<int, int> > s;
    s.push(make_pair(n - 1, a[n - 1]));

    for (int i = n - 2; i >= 0; i--){
        int t = 0;
        pair <int, int> 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;
}