看到“堆”这种形式，很容易让人联想到树状dp，但是，数据范围告诉我，没戏。
分析这题的特点，大约可以得到以下关键约束：
left<right<=root
换句话说，可以把所有的顶点排序，例如：
     a
    / \
   b   c
  /\   /\
 d  e f  g
则d<e<=b<f<g<=c<=a，
题目的意思就是修改某些值，使得这个式子成立。
怎么思考呢？
把题目的意思转化一下：保留数目尽量多的原始值，使得式子成立。
有思路了：
先把所有的＜号转化为≤：
d<=e-1<=b-1<=f-2<=g-3<=c-3<=a-3
然后，对
d e-1 b-1 f-2 g-3 c-3 a-3跑一个最长不降子序列就ok乐！

关键代码：
void dfs(int a){
	if (a>=N)return;
	dfs((a<<1)+1);
	if ((a<<1)+2<N)delta++;
	dfs((a<<1)+2);
	q[pt++]=A[a]-delta;
}
        dfs(0);
	ml=0;
	for (int i=0;i<N;i++){
		if (ml){
			if (mn[1]>q[i])tmp=1;
			else if (mn[ml]<=q[i])tmp=ml+1;
			else{
				l=1;r=ml;
				while (r>l+1){
					if (mn[(r+l)>>1]<=q[i])l=((r+l)>>1);
					else r=((r+l)>>1);
				}
				tmp=l+1;
			}
			if (tmp>ml)mn[++ml]=q[i];
			else if (mn[tmp]>q[i])mn[tmp]=q[i];
		}else{
			mn[ml=1]=q[i];
		}
	}
	printf("%d\n",N-ml);

• 大牛哇 数学知识超一流的大牛 (0) xuchang 2011-04-26 15:49:59
• 根据大牛的算法，果断地过掉了 (0) xuchang 2011-04-26 18:47:50