注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

POJ 3214  

2010-06-11 21:49:24|  分类: poj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目求改动尽可能少的节点,使得满足有序的性质,可以看出将改动后的树进行后续遍历后是一个非降的序列,但是有的是严格递增有的是不严格的,需要将某些值减小使得都是非严格的
  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
这样用O(nlogn)的最长非降子序列的算法就可以解决了
#include<cstdio> 
#include<iostream>
using namespace std;
int a[3000000],b[3000000],n,s[3000000],h,temp,tt=0,w=0;
int solve()
{
    int l,r,mid,len=1;
    a[1]=s[1];
    for(int i=2;i<=n;i++)
    {
           l=1,r=len;
           if(a[len]<=s[i]) 
        {
            a[++len]=s[i];
            continue;
        }
           while(l<=r)
           {
            mid=(l+r)>>1;
            if(a[mid]<=s[i]) l=mid+1;
            else r=mid-1;
           }
        a[l]=s[i];
        if(l>len) len++;
    }
    return len; 
}
 void dfs(int k){
  if(2*k+1<n)
dfs(2*k+1);
  if(2*k+2<n){
tt++;
dfs(2*k+2);
  }
s[++w]=b[k]-tt;
}
 int main(){
  scanf("%d",&h);
  while(scanf("%d",&temp)!=EOF)
b[n++]=temp;
dfs(0);
printf("%d\n",n-solve());
return 0;
 }
  评论这张
 
阅读(402)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018