(～ o ～)~zZ最长子序列。。。。。。
View Code
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 using namespace std;
5
6 struct box
7 {
8 int index;
9 int dm[12];
10 }b[40];
11 int num,dim;
12 int ins,maxn;
13 int dp[40];
14 int record[40];
15 int ans[40];
16
17 bool cmp(const box a,const box b)
18 {
19 for(int i = 0;i < dim;i ++)
20 {
21 if(a.dm[i] < b.dm[i])
22 return 1;
23 else if(a.dm[i] > b.dm[i])
24 return 0;
25 }
26 return 1;
27 }
28
29 bool feasibility(box a,box c)
30 {
31 for(int i = 0;i < dim;i ++)
32 {
33 if(a.dm[i]>= c.dm[i])
34 return false;
35 }
36
37 return true;
38 }
39
40 void getorder(int n,int i)
41 {
42 if(record[n] == n)
43 {
44 printf("%d ",n);
45 return;
46 }
47 getorder(record[n],i+1);
48 printf("%d",n);
49 if(i != 0)
50 printf(" ");
51 }
52
53 int main()
54 {
55 while(scanf("%d%d",&num,&dim) == 2)
56 {
57 for(int i = 1;i <= num;i ++)
58 {
59 record[i] = i;
60 for(int j = 0;j < dim;j ++)
61 {
62 scanf("%d",&b[i].dm[j]);
63 }
64 b[i].index = i;
65 sort(b[i].dm,b[i].dm + dim);
66 }
67
68 sort(b+1,b+num+1,cmp);
69 memset(dp,0,sizeof(dp));
70
71 maxn = 0;
72 //int ins;
73 for(int i = 1;i <= num;i ++)
74 {
75 dp[i] = 1;
76 for(int j = 1;j < i;j ++)
77 {
78 if(feasibility(b[j],b[i])&&dp[i] < dp[j] + 1)
79 {
80 dp[i] = dp[j] + 1;
81 record[b[i].index] = b[j].index;
82 }
83 }
84 if(maxn < dp[i])
85 {
86 maxn = dp[i];
87 ins = b[i].index;
88 }
89 }
90 printf("%d\n",maxn);
91 getorder(ins,0);
92 printf("\n");
93 }
94
95 return 0;
96 }