Hdu 1025

dp二分题目,WA点多多,下面一一阐述。

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int dp[500005];
int map[500005];
int main()
{
    int n,i,j,k,cases=0;
    int len,up,low,mid;
    while(~scanf("%d",&n))
    {
		cases++;
        int a,b;
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&a,&b);
            map[a]=b;
        }
        dp[1]=map[1];
        len=1;
        for(i=2;i<=n;i++)
        {
            low=1;
            up=len;
            while(low<=up)
            {
		mid=(up+low)/2;//一开始这条放在外面,死活T,二分不太熟悉,也是调了半天才发现
                if(dp[mid]<map[i])
                {
                    low=mid+1;
                }
                else
                {
                    up=mid-1;
                }
            }
            dp[low]=map[i];
            if(low>len)
            len++;
        }
		if(len==1)
			printf("Case %d:\nMy king, at most %d road can be built.\n\n",cases,len);//一条路和多条路不同没有s,其实仔细看题,题目也给出了
		else
			printf("Case %d:\nMy king, at most %d roads can be built.\n\n",cases,len);//每组样例间有回车符,最后结尾一定要有两个回车符
    }
    return 0;
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • POJ1837

    好巧妙的背包 杠杆原理:力臂=力距*力 当平衡时,左右的力臂相同,可以把左边的作为负的,右边的作为正的。 dp[i][j]表示用前i个钩码挂出力臂和为j的情况的...

    triplebee
  • Leetcode 279. Perfect Squares

    Given a positive integer n, find the least number of perfect square numbers (fo...

    triplebee
  • Leetcode 279. Perfect Squares

    Given a positive integer n, find the least number of perfect square numbers (fo...

    triplebee
  • 从Native到Web(五), emscripten学习笔记: 初体验

    逍遥剑客
  • C语言中不同变量的访问方式

    C语言中的变量大致可以分为全局变量,局部变量,堆变量和静态局部变量,这些不同的变量存储在不同的位置,有不同的生命周期。一般程序将内存分为数据段、代码段、栈段、堆...

    Masimaro
  • 彻底搞定C语言指针(精华版)

    1.语言中变量的实质 要理解C指针,我认为一定要理解C中“变量”的存储实质, 所以我就从“变量”这个东西开始讲起吧! 先来理解理解内存空间吧!请看下图: ...

    Angel_Kitty
  • 《大话计算机》之:趣味了解浮点数(下)

    由ssdfans团队所著《深入理解SSD》一书已经出版电子版,详情及购买见固态硬盘掉电怎么恢复数据一文结尾。将本帖转发到朋友圈并截图发到本公众号首页窗口,冬瓜哥...

    冬瓜哥
  • 从线条艺术到DIY实现一个网状体Net的js库

    今天无意中看到一个可视化作品: WHAT MADE ME? INTERACTIVE PUBLIC INSTALLATION Most Original Exh...

    mixlab
  • JavaScript与有限状态机

    有限状态机(Finite-state machine)是一个非常有用的模型,可以模拟世界上大部分事物。 ? 简单说,它有三个特征:   * 状态总数(stat...

    ruanyf
  • Context都没弄明白,还怎么做Android开发?

    作为Android开发者,不知道你有没有思考过这个问题,Activity可以new吗?Android的应用程序开发采用JAVA语言,Activity本质上也是一...

    Android技术干货分享

扫码关注云+社区

领取腾讯云代金券