uva 103 - Stacking Boxes

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 int dj[100][100],num[100][100],d[100];
 5 int m,n;
 6 int prenum[100];
 7 int distanc(int a){           //动态规划的方法仿照上一题
 8     if(d[a]>-1)
 9         return d[a];
10     for(int i=0;i<m;i++){
11         if(i==a)
12             continue;
13         if(dj[a][i]){
14             if(d[a]<1+distanc(i)){
15                 d[a]=1+distanc(i);
16                 prenum[a]=i;        //这里保存前一个状态
17             }
18         }
19         else
20             continue;
21     }
22     if(d[a]==-1)
23         d[a]=1;
24     return d[a];
25 }
26 int main(){
27     
28     while(cin>>m>>n){
29         for(int i=0;i<m;i++){
30             for(int j=0;j<n;j++){
31                 cin>>num[i][j];
32             }
33             sort(&num[i][0],&num[i][n]);
34             d[i]=-1;
35             prenum[i]=-1;
36         }
37         for(int i=0;i<m;i++){
38             for(int j=0;j<m;j++){
39                 if(i==j){
40                     dj[i][i]=1;
41                     continue;
42                 }
43                 dj[i][j]=dj[i][j]=0;
44                 for(int k=0;k<n;k++){
45                     if(num[i][k]<num[j][k]){
46                         dj[i][j]=1;            
47                     }
48                     else{
49                         dj[i][j]=0;
50                         break;
51                     }
52                 }
53             }
54         }
55         int maxnum=0;
56         int temp=0;
57         for(int i=0;i<m;i++){
58             if(maxnum<distanc(i)){
59                 maxnum=distanc(i);
60                 temp=i;
61             }
62         }
63         cout<<maxnum<<endl;
64         cout<<temp+1;
65         while(prenum[temp]!=-1){
66             
67             temp=prenum[temp];
68             cout<<" "<<temp+1;
69         }
70         cout<<endl;
71     }
72 }