POJ 3183 - Stump Removal

http://poj.org/problem?id=3183

概要

N 個のスタンプがあり，最小の爆薬ですべてのスタンプを爆破したい．

i 番目のスタンプの上に爆薬を落とすとそのスタンプを爆破できる．

また，高さ H のスタンプが爆破されると，それに隣接した高さ H 未満のスタンプも連鎖的に爆破される．

制約

• 1 <= N <= 50000
• 1 <= H[i] <= 10000

解法

H[i-1] <= H[i] && H[i] >= H[i+1] なスタンプ i は連鎖的に爆破されないので，爆薬を使うしかない．

逆に，そうでないスタンプは隣接するスタンプから連鎖的に爆破されるので，爆薬を使う必要はない．

1 N,x,y,z;main(i){scanf("%d",&N);for(scanf("%d",&y);i<=N;i++){scanf("%d",&z);x<=y&&y>=z&&printf("%d\n",i);x=y;y=z;}}