正文
Codeforces Round #189 (Div. 2) D. Psychos in a Line 单调队列dp
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
D. Psychos in a Line
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
There are n psychos standing in a line. Each psycho is assigned a unique integer from 1 to n. At each step every psycho who has an id greater than the psycho to his right (if exists) kills his right neighbor in the line. Note that a psycho might kill and get killed at the same step.
You're given the initial arrangement of the psychos in the line. Calculate how many steps are needed to the moment of time such, that nobody kills his neighbor after that moment. Look notes to understand the statement more precise.
Input
The first line of input contains integer n denoting the number of psychos, (1 ≤ n ≤ 105). In the second line there will be a list of n space separated distinct integers each in range 1 to n, inclusive — ids of the psychos in the line from left to right.
Output
Print the number of steps, so that the line remains the same afterward.
Examples
input
10
10 9 7 8 6 5 3 4 2 1
output
2
input
6
1 2 3 4 5 6
output
0
Note
In the first sample line of the psychos transforms as follows: [10 9 7 8 6 5 3 4 2 1] → [10 8 4] → [10]. So, there are two steps.
题意：给你n个人，每个人有个权值a[i]，如果当前a[i]>a[i+1]则可以杀死右边的人，可以同时杀死；
求无法杀人的时间；
思路：dp[i]表示i可以杀死右边的人需要的时间；
从后往前
需要维护一个单调递减的序列；
如果你右边的人dp[i+1]需要t时间；
然后你杀死它只需要一秒，你需要t时间替他杀完那多出来的人；
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define pi (4*atan(1.0))
#define eps 1e-14
#define bug(x) cout<<"bug"<<x<<endl;
const int N=1e5+,M=1e6+,inf=;
const ll INF=1e18+,mod=;
int a[N],dp[N];
int q[N];
int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
int head=,tail=;
int ans=;
for(int i=n;i>=;i--)
{
int sum=;
while(tail<=head&&a[i]>a[q[head]])
{
sum++;
sum=max(sum,dp[q[head]]);
dp[i]=max(sum,dp[q[head]]);
head--;
}
ans=max(ans,dp[i]);
q[++head]=i;
}
printf("%d\n",ans);
}
return ;
}
/*
10
10 7 4 2 5 8 9 6 3 1
4 2 1 0 0 0 1 1 1 0
4
*/
