Codeforces Round #189 (Div. 1) B:http://codeforces.com/problemset/problem/319/B
题意：每一ROUND如果某个人的数字大于他右边的人，他就会干掉右边的人，一个人可以同时干掉别人和被干掉，问要多少ROUND结束后才不会死人。
题解：第一次接触传说中的单调队列，自己觉得这一题还是dp占主要部分。还是那就话，dp就是一种艺术。f[i]表示的是被第几次杀死，f[i]=f[j]+1;(j表示i左边的比i小的数)，不过这里处理dp，还要维护一下单调队列，对于i后面的元素k来说，k被杀死的时候，一定与i前面的比i小的元素没有关系，因为i被他们大，如果前面比i小的数都能杀死k，那么i肯定能杀死k，所以i前比i小的元素，在后面的遍历中用不上。所以直接删除，减少不必要的运算和判断。
1 #include <cstdio> 2 #include <vector> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 #define N 100005 7 vector<int> v; 8 int f[N], n, t, cnt; 9 int main() { 10 scanf("%d", &n); 11 memset(f, 0, sizeof(f)); 12 for (int i=0; i<n; i++) { 13 scanf("%d", &t); 14 cnt = 0; 15 if (v.size() == 0) { v.push_back(t); continue; } 16 while (v.back() < t) { 17 cnt = max(cnt, f[v.back()]); 18 v.pop_back(); 19 if (v.size() == 0) break; 20 } 21 if (v.size() == 0) { v.push_back(t); continue; } 22 f[t] = cnt + 1; 23 v.push_back(t); 24 } 25 int ans = 0; 26 for (int i=0; i<n; i++) ans = max(ans, f[i]); 27 printf("%d\n", ans); 28 return 0; 29 }
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<algorithm> 6 using namespace std; 7 int n,ans,flag; 8 int a[100005],b[100005],xb[100005]; // a[]-存输入的数据 9 // b[]-存需要几次操作将他杀掉 xb[]-存杀掉第i个人的人的下标 10 void solve(){ 11 int i,j,ma; 12 ans=-1; 13 b[1]=xb[1]=0; // 默认b[1]杀不掉 14 for(i=2; i<=n; i++){ //从第二个开始判断 15 ma=0; 16 flag=0; // 存a[i]是否能被杀掉 17 j=i-1; 18 while(a[j]<a[i]&&j){ 19 if(!b[j]){ // 如果a[j]不能被前面人杀掉 则a[i]也不能 20 flag=1; 21 break; 22 } 23 if(b[j]>ma) ma=b[j]; 24 j=xb[j]; // 跳转到杀死a[j]的人 25 } 26 if(!flag) b[i]=ma+1; //如果被杀死 则需ma+1步 27 else b[i]=0; // 没被杀死则需要0步 28 xb[i]=j; // 记录是谁杀死他的 29 } 30 for(i=1; i<=n; i++){ 31 if(ans<b[i]) ans=b[i]; 32 } 33 } 34 int main(){ 35 int i,j; 36 while(~scanf("%d",&n)){ 37 for(i=1; i<=n; i++){ 38 scanf("%d",&a[i]); 39 } 40 solve(); 41 printf("%d\n",ans); 42 } 43 return 0; 44 }