hdu 1025 lis 注意细节！！！【dp】

感觉这道题浪费了我半个小时的生命。。。。。。哇靠！原来输出里面当len=1时是road否则是roads！！！

其实做过hdu 1950就会发现这俩其实一样，就是求最长上升子序列。我用结构体记录要连线的两个city，对一个数组排序再求相应的另一个数组lis。开始WA还以为我写错了，造了数据测一下没错啊。。。又想是不是情况没考虑全，比如一个城市可以连好多城市，好多城市可以连一个城市？？？巴拉巴拉。。。后来发现只可以一对一啊。。。。死在这种细节上真的是欲哭无泪。。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int INF=0x3f3f3f3f;
 7 const int MAXN = 500050;
 8 struct Node{
 9     int p,r;
10 };
11 Node a[MAXN];
12 int dp[MAXN],t[MAXN];
13 int len=1;
14 
15 bool cmp(Node a,Node b)
16 {
17     if(a.p==b.p)
18         return a.r<b.r;
19     return a.p<b.p;
20 }
21 
22 int bin_search(int key)
23 {
24     int low,high,mid;
25     low=0,high=len;
26     while(low<high)
27     {
28         mid=(low+high)>>1;
29         if(t[mid]>=key)
30             high=mid;
31         else low=mid+1;
32     }
33     return low;
34 }
35 
36 int main()
37 {
38     int N;
39     int cas=1;
40     while (scanf("%d", &N) == 1)
41     {
42         for (int i = 0; i < N; i++) {
43             scanf("%d%d",&a[i].p,&a[i].r);
44             dp[MAXN]=INF;
45         }
46         sort(a,a+N,cmp);
47         len=1;
48         t[0]=a[0].r;
49         for(int i=1;i<N;i++){
50             if(a[i].r>t[len-1])
51                 t[len++]=a[i].r;
52             else{
53                 int pos=bin_search(a[i].r);
54                 t[pos]=a[i].r;
55             }
56         }
57         if(len==1)
58 
59         printf("Case %d:
My king, at most %d road "
60               "can be built.

",cas++,len);
61         else
62         printf("Case %d:
My king, at most %d roads "
63               "can be built.

",cas++,len);
64     }
65     return 0;
66 }