Mary在她的生日礼物中有一些积木。那些积木都是相同大小的立方体。每个积木上面都有一个数。Mary用他的所有积木垒了一个高塔。妈妈告诉Mary游戏的目的是建一个塔，使得最多的积木在正确的位置。一个上面写有数i的积木的正确位置是这个塔从下往上数第i个位置。Mary决定从现有的高塔中移走一些，使得有最多的积木在正确的位置。请你告诉Mary她应该移走哪些积木。
第一行为一个数n，表示高塔的初始高度。第二行包含n个数a1,a2,...,an，表示从下到上每个积木上面的数。(1<=n<=100000,1<=ai<=1000000)。
注意：请输出最多有多少点可以处在正确位置
设ai为第i个数字，si = i-ai
当且仅当 si<=sj && ai<=aj 才能满足第i和第j块积木都能放到正确的位置上
这就变成了一个二维偏序的问题了，也很像LIS，用树状数组处理就OK
#include<stdio.h> #include<algorithm> using namespace std; typedef struct Res { int x, y; bool operator < (const Res &b) const { if(x<b.x || x==b.x && y<b.y) return 1; return 0; } }Res; Res s[100005]; int n, tre[100005], dp[100005]; int Query(int k) { int ans = 0; if(k==0) return 0; while(k) { ans = max(ans, tre[k]); k -= k&-k; } return ans; } void Update(int k, int x) { while(k<=n) { tre[k] = max(tre[k], x); k += k&-k; } } int main(void) { int i, x, ans; scanf("%d", &n); for(i=1;i<=n;i++) { scanf("%d", &x); s[i].x = i-x; s[i].y = x; } ans = 0; sort(s+1, s+n+1); for(i=1;i<=n;i++) { if(s[i].x<0) continue; dp[i] = Query(s[i].y-1)+1; Update(s[i].y, dp[i]); ans = max(ans, dp[i]); } printf("%d\n", ans); return 0; }