hdu_1025(LIS Nlog(N)算法)

题意：自己慢慢读吧。大概就是道路两边建路，给出建路需求，要求两条路不能有交叉，问最多可以建多少条路。

题解：一看数据范围500000，应该是dp，再画个图模拟一下，发现实质就是求最长上升子序列，很自然的数据要求nlogn算法

算法讲解在之前写过，这里直接贴过来：点我哦

坑：输出两个坑，一个是road和roads的区别，还有一个是案例之间有空行

code:

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N = ;

 int q[N];

 int stk[N];

 int BSearch(int l,int r, int c)

 {

     while(l<=r){//注意这里应该是定于的时候还要再判断一次。

         int m = (l+r)>>;

         if(stk[m]==c) {

             //printf("id = %d\n",m);

             return m;

         }

         else if(stk[m]<c) l = m+;

         else if(stk[m]>c) r = m-;

     }

     //printf("id = %d\n",l);

     return l;

 }

 int main()

 {

     int n;

     int c = ;

     while(~scanf("%d",&n))

     {

         int cnt = ;

         int t1,t2;

         memset(stk,-,sizeof(stk));

         for(int i = ; i < n; i++){

             scanf("%d%d",&t1,&t2);

             q[t1] = t2;

         }

         for(int i = ; i <= n; i++){

             if(q[i]>stk[cnt-]){

                 stk[cnt++] = q[i];

             }

             else {

                 int id = BSearch(,cnt-,q[i]);

                 stk[id] = q[i];

             }

         }

         cnt--;

         if(cnt!=)

             printf("Case %d:\nMy king, at most %d roads can be built.\n\n",c++,cnt);

         else

             printf("Case %d:\nMy king, at most %d road can be built.\n\n",c++,cnt);

     }

     return ;

 }

巴特西

hdu_1025(LIS Nlog(N)算法)

最新文章

热门文章