HDU 1025 Constructing Roads In JGShining's Kingdom

分手后的思念是犯贱 2022-04-15 04:15 149阅读 0赞

## 原题目链接：[HDU1025][] ##

--------------------

## 分类 ##

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

--------------------

## 题意 ##

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

--------------------

## 样例输入输出 ##

Sample Input

2 
    1 2 
    2 1 
    3 
    1 2 
    2 3 
    3 1 
    5 
    2 2 
    3 3 
    4 1 
    1 4 
    5 5

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;
    }

--------------------

[HDU1025]: http://acm.hdu.edu.cn/showproblem.php?pid=1025
[HDU1025 1]: https://blog.csdn.net/liurui39660/article/details/51899942