acm动态规划之最长路问题UVA103stocking boxes做题报告

在这个问题中，你要分析一组n维盒子的某个性质。你要确定出盒子的最长嵌套串，也就是说一系列的盒子b₁、b₂、……、b_k，一个套一个，使所有的b_i都嵌套在b_i+1内。

对于一个盒子D = (d₁, d₂, ..., d_n)和另一个盒子E = (e₁, e₂, ..., e_n)，如果存在一种d_i的排列，使重排的每个维度的值都小于盒子E中对应维度的值，则盒子D可嵌入盒子E。这个过程和旋转盒子D，看它是否能套入E的过程类似。然而，若需满足所有维度的排列，盒子D必须是可以扭曲的，而不仅仅是旋转。

定义嵌套关系如下：盒子D = (d₁, d₂, ..., d_n)和E = (e₁, e₂, ..., e_n)，当存在一种1...n的排列p使得(d_p(1), d_p(2), ..., d_p(n))能够匹配(e₁, e₂, ..., e_n)，即对所有的1 ≤ i ≤ n都有d_p(i) < e_i，那么就认为D可以嵌入E。

输入由一组的盒子序列构成。每个盒子序列的开始是盒子的总数k和维度n（出现在同一行）。

第一行下面有k行，每行用n个（n由第一行确定）数表示一个盒子，这n个数由一个或多个空格隔开。序列中的第i行（1 ≤ i ≤ k）表示第i个盒子。

输入的数据中可能存在多个盒子序列。你的程序应该处理全部数据，针对每个序列，找出k个盒子中的哪几个可以构成最长的嵌套串，以及这个嵌套串的长度（嵌套串中盒子的数量）。

在这个问题中最大的维度是10，最小的维度是1。最大的盒子序列长度为30。

输出

对应输入的每个盒子序列，应在第一行输出最长的嵌套串长度，在下一行按顺序输入组成这个嵌套串的盒子列表。嵌套串中最“小”的或着说是最“内”的盒子应该放在第一位，之外的一个（如果存在）放在第二位，以此类推。

盒子的编号要按它们在输入数据中的位置相对应。（输入的第一个盒子为1号，第二个盒子为2号，等等）

如果存在多于一个嵌套串的长度同为最长，可输出其中的任何一个。

题目分析：

盒子嵌套关系是一个典型的有向无环图模型这个要先建立这个图然后再来找最长路；这样时间复杂度会降低; 建图的时间复杂度o(n^3)太大了看一看有没有别的办法;

然后找最大串,就是遍历所有向他入的结点,找到最大的加一，这样时间复杂度是o(n^2); 在这个过程中同时用数组记下最长路;用空间来换时间; 只需要开一个数组存储每一个结点的上一个结点，然后输出的时候用递归从头输出, 这时候时间复杂度从o(n^2)到o(n)

代码如下

  1 /*
  2 盒子嵌套关系是一个典型的有向无环图模型
  3 这个要先建立这个图然后再来找最长路；这样时间复杂度会降低;
  4 建图的时间复杂度o(n^3)太大了 看一看有没有别的办法; 
  5 
  6 然后找最大串,就是遍历所有向他入的结点,找到最大的加一，这样时间复杂度是o(n^2);
  7 在这个过程中同时用数组记下最长路;用空间来换时间; 只需要开一个数组存储每一个结点的上一个结点，
  8 然后输出的时候用递归从头输出, 这时候时间复杂度从o(n^2)到o(n) 
  9 */
 10 //
 11 #include <set>
 12 #include <map>
 13 #include <cmath>
 14 #include <queue>
 15 #include <stack>
 16 #include <string>
 17 #include <vector>
 18 #include <cstdio>
 19 #include <cstring>
 20 #include <iostream>
 21 #include <algorithm>
 22 
 23 using namespace std;
 24 typedef long long ll;
 25 typedef unsigned long long ull;
 26 
 27 #define debug puts("here")
 28 #define rep(i,n) for(int i=0;i<n;i++)
 29 #define rep1(i,n) for(int i=1;i<=n;i++)
 30 #define REP(i,a,b) for(int i=a;i<=b;i++)
 31 #define foreach(i,vec) for(unsigned i=0;i<vec.size();i++)
 32 #define pb push_back
 33 #define RD(n) scanf("%d",&n)
 34 #define RD2(x,y) scanf("%d%d",&x,&y)
 35 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
 36 #define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)
 37 #define zero(x,y) memset(x,0,y)
 38 #define nega_1(x,y) memset(x,-1,y)
 39 
 40 const int MAX=50;
 41 int G[MAX][MAX];//记录有向图信息;0表示没有关系，1表示i把j嵌套之，-1表示没有访问 
 42 int box[MAX][MAX];// 保存图的信息; 
 43 int longest[MAX];//记录每个结点的前一个最长结点;
 44 int leng_th[MAX];//记录每个结点的最长长度; 
 45 int vis[MAX];//记录有没有访问过; 
 46 int n,k;
 47 int long_path(int i)
 48 {
 49     int j;
 50     if(vis[i])return leng_th[i];
 51     vis[i]=1;
 52     rep(j,n)
 53     {
 54         if(G[i][j]==1&&leng_th[i]<=long_path(j)+1)
 55         {
 56             leng_th[i]=long_path(j)+1;
 57             longest[i]=j;        
 58         }
 59     }
 60     return leng_th[i];
 61 }
 62 void print_path(int i)
 63 {
 64     //递归终点是找到-1；
 65     if(i==-1)return;
 66     print_path(longest[i]);
 67     cout<<i+1<<" "; 
 68 }
 69 int main()
 70 {
 71     #ifndef ONLINE_JUDGE
 72     freopen("F://code//txt//24.txt","r",stdin);
 73     #endif
 74     //int n,k;//n表示行数，k表示箱子纬度个数;
 75     int i,j,m,w;
 76     while(cin>>n>>k)
 77     {
 78         rep(i,n)
 79         {
 80             rep(j,k)
 81             {
 82                 cin>>box[i][j];
 83             }
 84         }//读完了所有的图信息;
 85         //开始构造图，用邻接矩阵;
 86         nega_1(G,sizeof G);
 87         rep(i,n)
 88             sort(box[i],box[i]+k);
 89         rep(i,n)
 90         {
 91             rep(j,n)
 92             {
 93                 if(i==j)
 94                 {
 95                     G[i][j]=0;
 96                     continue;
 97                 }
 98                 if(G[i][j]==-1)
 99                 {
100                     int success=1;
101                     rep(m,k)
102                     if(box[i][m]<=box[j][m])
103                     {
104                         success=0;
105                         break;
106                     }
107                     if(success)
108                     {
109                         G[i][j]=1;
110                         G[j][i]=0;
111                     
112                     }
113                     else
114                         G[i][j]=0;
115                 } 
116             }
117         }//图建立完成 
118         //使用递归进行;找最长路; 
119         zero(vis,sizeof vis);
120         nega_1(longest,sizeof longest);//为了防止0的重复; 
121         zero(leng_th,sizeof leng_th);
122         
123         rep(i,n)
124         {
125             long_path(i);
126         }//求最长路;
127         int longest_len=0;
128         int end_point;
129         rep(i,n)
130          if(longest_len<leng_th[i])
131          {
132              longest_len=leng_th[i];
133              end_point=i;
134           } 
135          cout<< longest_len+1<<endl;
136          print_path(end_point);
137          cout<<endl;
138         
139     } 
140     return 0;
141 }