hdu1025

#include<stdio.h> const int MAXN=500010; int a[MAXN],b[MAXN];

//用二分查找的方法找到一个位置,使得num>b[i-1] 并且num<b[i],并用num代替b[i] int Search(int num,int low,int high) { int mid; while(low<=high) { mid=(low+high)/2; if(num>=b[mid]) low=mid+1; else high=mid-1; } return low; } int DP(int n) { int i,len,pos; b[1]=a[1]; len=1; for(i=2;i<=n;i++) { if(a[i]>=b[len])//如果a[i]比b[]数组中最大还大直接插入到后面即可 { len=len+1; b[len]=a[i]; } else//用二分的方法在b[]数组中找出第一个比a[i]大的位置并且让a[i]替代这个位置 { pos=Search(a[i],1,len); b[pos]=a[i]; } } return len; } int main() { int n; int iCase=0; int i,j; int x,y; while(scanf("%d",&n)!=EOF) { iCase++; for(i=1;i<=n;i++) { scanf("%d%d",&x,&y); a[x]=y; } int res=DP(n); printf("Case %d:\n",iCase); if(res==1) { printf("My king, at most 1 road can be built.\n\n"); } else printf("My king, at most %d roads can be built.\n\n",res); } return 0; }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • hdu1017

    @坤的
  • hdu1040

    @坤的
  • hdu1049

    @坤的
  • 洛谷P4425 [HNOI/AHOI2018]转盘(线段树)

    首先猜一个结论:对于每次询问,枚举一个起点然后不断等到某个点出现时才走到下一个点一定是最优的。

    attack
  • HDU4352 XHXJ's LIS(LIS 状压)

    刚开始的思路是$f[i][j]$表示到第$i$位,LIS长度为$j$的方案。 然而发现根本不能转移,除非知道了之前的状态然后重新dp一遍。。

    attack
  • BZOJ4299: Codechef FRBSUM(主席树)

    那么若$a[i + 1] > s_i + 1$,那么$a[i + 1]$不能被拼成

    attack
  • 2019HDU多校赛第二场 HDU 6601 Keen On Everything But Triangle( 主席树求区间第k大)

    用户2965768
  • poj----1330Nearest Common Ancestors(简单LCA)

    题目连接  http://poj.org/problem?id=1330 就是构建一棵树,然后问你两个节点之间最近的公共父节点是谁? 代码: 1 /*Sour...

    Gxjun
  • HDU 6621 (2019杭电第四场 1008) K-th Closest Distance (主席树 + 二分, 求第 k 小绝对值)

    题意:给出n m, 表示n个数,m组询问, 每组询问给出 l , r , p ,k 四个数,求[L,R]区间内 |p - a[i]|值第 k 小的数

    用户2965768
  • CodeForces #549 Div.2 C Queen

    ShenduCC

扫码关注云+社区

领取腾讯云代金券