HDU 1025 Constructing Roads In JGShining's Kingdom-蒲公英云

HDU 1025 Constructing Roads In JGShining's Kingdom

原题目链接：HDU1025

分类

HDU 动态规划最长上升子序列

题意

两条平行线上有若干个点从左向右依次排开，给定若干条分别以两条平行线上已知点为端点的线段，取其中若干条互不相交的线段，问最多可取多少条，这里有个题解讲的很好，拿来用HDU1025题解

样例输入输出

Sample Input

Sample Output

Case 1: 
My king, at most 1 road can be built.
Case 2: 
My king, at most 2 roads can be built.
Case 3: 
My king, at most 3 roads can be built.

想法

最长上升子序列变形
求lis，n^2或nlogn的DP方法都有，额倒是没看那些，寻了一个以栈结构解决的方法，做法很简单，每次遇到一个数，比栈顶的数大就压栈，否则就（二分）找到比这个数大的第一个数，用这个数替换之，最后输出栈的长度即可，为何此法可行，不难看出，栈内部有序，栈顶最大，若遇到更大的数便压栈，最大长度自然也+1了，至于替换，可以理解为降低了后面的数再压栈时的门槛，但同时最大长度没变，例如，如果栈中是1,5，遇见一个3，最大长度没有提升，若栈是1,2，遇见3则会有所提升，而从1,5到1,2，只要在3之前遇到一个2即可，这个2便降低了压栈的门槛，使得3可以进入
不过需要注意，最后栈里的结果并非所求最长子序列，比如输入为2,3,4,1，最后栈内为1,3,4，不难理解，1的加入并没有考虑到会修改已经成型的栈内结果，因而这种方法只能求得其长度，而得不到其本身

代码

/** * Author: GatesMa * Email: gatesma@foxmail.com * Todo: ACM Training * Date:2018/11/21 */
#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn = 555555; 
int dp[maxn];//模拟的栈 因为stl的栈没给迭代器 没法二分
int roads[maxn]; //模拟线段，下标和值分别代表两个端点序号 
int n; 
int top;//栈顶下标
int kase = 0;
int main()
{ 
    while(cin >> n){ 
        top = 0;
        for(int i=0;i<n;i++){ 
            int a,b;
            cin >> a >> b;
            roads[b]  = a;//输入是按顺序排的，这样可以少排序操作 
        }
        memset(dp, 0 ,sizeof(dp));
        for(int i=1;i<=n;i++){ 
            if(roads[i] > dp[top]){ 
                dp[++top] = roads[i];
            }else{ 
                *lower_bound(dp, dp + top, roads[i]) = roads[i];
            }
        } 
        if (top == 1)//下面是应对坑人格式所做的输出
        printf("Case %d:\nMy king, at most %d road can be built.\n\n", ++kase, top);
        else
        printf("Case %d:\nMy king, at most %d roads can be built.\n\n", ++kase, top);
    }
    return 0;
}