HDU 1160 排序或者通过最短路两种方法解决

题目大意:

给定一堆点，具有x，y两个值

找到一组最多的序列，保证点由前到后，x严格上升，y严格下降，并把最大的数目和这一组根据点的编号输出来

这里用两种方法来求解：

我们可以一开始就将数组根据x由大到小排个序，由前往后取，保证x严格上升了

只要每次取得过程中找一条x不相等的关于y的最长下降子序列即可，加个回溯，输出所有点

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int N = ;

 int dp[N] , fa[N] , rec[N];

 struct Node{

     int x , y , id;

     bool operator<(const Node &m)const{

         if(x == m.x) return y < m.y;

         return x < m.x;

     }

 }node[N];

 int main()

 {

     //freopen("a.in" , "r" , stdin);

     int k = ;

     while(scanf("%d%d" , &node[k].x , &node[k].y) != EOF){

         node[k].id = k + ;

         k++;

     }

     //先保证都是以x由小到大排列

     sort(node , node+k);

     memset(dp ,  , sizeof(dp));

     memset(fa , - , sizeof(fa));

     dp[] = ;

     //x已满足上升，现在处理y使其按下降顺序排列即可，按照最长上升子序列的O(n^2)的方法类似处理即可

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

         dp[i] = ;

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

             if(node[j].x != node[i].x && node[i].y < node[j].y){

                 if(dp[i] < dp[j] + ){

                     dp[i] = dp[j] + ;

                     fa[i] = j;

                 }

             }

         }

     }

     int maxn =  , la;

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

         if(maxn < dp[i]) maxn = dp[i] , la = i;

     }

     int cnt = ;

     rec[cnt++] = la;

     while(fa[la] >= ){

         rec[cnt++] = fa[la];

         la = fa[la];

     }

     printf("%d\n" , maxn);

     for(int i =cnt- ;  i>= ; i--)

         printf("%d\n" , node[rec[i]].id);

     return ;

 }

我们对所有m1.x<m2.x , m1.y>m2.y的m1和m2间添加一条有向线段

这样我们可以从所有入度为0的点出发，进行bfs，每一条边认为长度为1，入度为0的点认为dp[i] = 1表示到达第i个点最多能有多少个物品

计算最短路径的过程加个回溯这个题目就解决了

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <queue>

 #include <iostream>

 using namespace std;

 const int N = ;

 int dp[N] , fa[N] , rec[N] , k , t , first[N];

 int in[N] , vis[N];

 queue<int> q;

 struct Node{

     int x , y , id;

     bool operator<(const Node &m)const{

         if(x == m.x) return y < m.y;

         return x < m.x;

     }

 }node[N];

 struct Edge{

     int y , next;

 }e[N*N];

 void add_edge(int x, int y)

 {

     e[k].y = y , e[k].next = first[x];

     first[x] = k++;

 }

 void bfs(int s)

 {

     memset(vis ,  , sizeof(vis));

     q.push(s);

     vis[s] = ;

     while(!q.empty()){

         int u = q.front();

         q.pop();

         vis[u] = ;

         for(int i = first[u] ; i!=- ; i = e[i].next){

             int v = e[i].y;

             if(dp[v] < dp[u] + ){

                 dp[v] = dp[u] + ;

                 fa[v] = u;

                 if(!vis[v]){

                     vis[v] = ;

                     q.push(v);

                 }

             }

         }

     }

 }

 bool ok(int ith1 , int ith2)

 {

     return node[ith1].x < node[ith2].x && node[ith1].y > node[ith2].y;

 }

 int main()

 {

    // freopen("a.in" , "r" , stdin);

     t =  , k = ;

     memset(first , - , sizeof(first));

     memset(dp ,  , sizeof(dp));

     memset(in ,  , sizeof(in));

     while(scanf("%d%d" , &node[t].x , &node[t].y) != EOF){

         node[t].id = t + ;

         t++;

     }

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

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

             if(ok(i , j)){

                 add_edge(i , j);

                 in[j] ++;

             }

             if(ok(j , i)){

                 add_edge(j , i);

                 in[i] ++;

             }

         }

     }

     for(int i =  ; i<t ; i++)

         if(in[i] == ){

             dp[i] = ;

             bfs(i);

         }

     int maxn =  , la;

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

         if(maxn < dp[i]){

             maxn = max(maxn , dp[i]);

             la = i;

         }

     }

     int cnt = ;

     rec[cnt++] = la;

     while(fa[la]){

         rec[cnt++] = fa[la];

         la = fa[la];

     }

     printf("%d\n" , maxn);

     for(int i = cnt- ; i>= ; i--)

         printf("%d\n" , rec[i]);

     return ;

 }

巴特西

HDU 1160 排序或者通过最短路两种方法解决

最新文章

热门文章