Constructing Roads In JGShining’s Kingdom

problem link

The meaning of the problem

So why this is longest increasing subsequence Problem ? Look at the picture below:

hdu1025

As the problem described, we can’t have crossed lines. Each line has two endpoints. One is the “rich” endpoint above and the other is the “poor” endpoint below. The rich endpoints’ number of the lines we finally pick up should be monotonically increasing. The corresponding poor endpoints should be monotonically increasing too. Otherwise the lines will be crossed.

Let’s use a[p]=q to represent that the p city can link q city. Then the problem tend to become a question of longest increasing subsequence.

The Algorithm

There is a quite easy way to understand the LIS problem. I learned it from this tutorial

A clever approach. Create a new array cell to store the longest increasing subsequence.

Iterate through the original sequence, and binary insert each element into cell.

If all the elements in cell are smaller than the current one, append it at the end.
Otherwise, replace the smallest element in cell that is larger than the current one.
In short, the idea is to keep cell storing relatively smaller elements. Although cell may not represent the actual longest increasing subsequence, its length is correct.

Author: ColdMe
Link: https://leetcode.cn/problems/longest-increasing-subsequence/solutions/13118/zui-chang-shang-sheng-zi-xu-lie-dong-tai-gui-hua-e/
Source: LeetCode
Copyright belongs to the author. For commercial use, please contact the author for authorization. For non-commercial use, please credit the source.

There are ways to prove that the cell array is monotonically increasing. Anything detailed you can see Wikipedia

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<cstdio>
#include<map>
#include<cmath>
#include<string>
#include<algorithm>
#include<iomanip>
using namespace std;
const int mxlen = 5e5+5;
int n;
int seq[mxlen];
int a[mxlen];
int main(){
    int cnt = 0;
    while(scanf("%d",&n)!=EOF){
        int x,y;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&x,&y);
            a[x]=y;
        }
        memset(seq,0,sizeof(seq));
        int len = 0;
        for(int i=1;i<=n;i++){
            if(a[i]>seq[len]){
                seq[++len] = a[i];
            }else {
                int l=1,r=len;
                while(l<=r){
                    int mid = (l+r)>>1;
                    if(seq[mid]>=a[i]) r = mid-1;
                    else l = mid+1;
                }
                seq[l] = a[i];
            }
        }
        // When the number of roads is greater than 2, an s needs to be added after the road.
        if(len==1) printf("Case %d:\nMy king, at most 1 road can be built.\n\n",++cnt);
        else printf("Case %d:\nMy king, at most %d roads can be built.\n\n",++cnt,len);
    }
    return 0;
}