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 =  + ;
int a[maxn];
int dp[maxn];
int n; void solve(){
memset(dp, , sizeof(dp));
stack <pair<int, int> > s;
s.push(make_pair(n - , a[n - ])); for (int i = n - ; i >= ; i--){
int t = ;
pair <int, int> p;
while (!s.empty() && s.top().second < a[i]){
p = s.top();
t = max(dp[p.first], t + );
s.pop();
}
s.push(make_pair(i, a[i]));
dp[i] = t;
}
int cnt = ;
for (int i = ; i < n; i++) cnt = max(cnt, dp[i]);
cout << cnt << endl;
} int main(){
while (scanf("%d", &n) == ){
for (int i = ; i < n; i++) scanf("%d", a + i);
solve();
}
return ;
}
上一篇:服务端NETTY 客户端非NETTY处理粘包和拆包的问题


下一篇:Eclipse开发工具的使用之-使用Eclipse的Debug调试Android程序