uva103(最长递增序列，dag上的最长路）
题目的意思是给定k个盒子，每个盒子的维度有n dimension
问最多有多少个盒子能够依次嵌套
但是这个嵌套的规则有点特殊，两个盒子，D = （d1,d2,...dn) ,E = (e1,e2...en) 只要盒子D的任意全排列，小于盒子E，那么就说明
盒子D能放入盒子E中，其实就是将两个盒子的维度排序，如果前一个盒子的维度依次小于后一个盒子，那么就说明前一个盒子能放入后一个盒子中
这个题目能够转化为最长递增子序列。
首先将盒子的维度从小到大排序，然后将k个盒子，按照排序后的第一维度从小到大排序
这样中的目的是，后面的盒子一定放不到前面的盒子里面，这样是为了消除无后效性。
如果不排序，那么将有后效性，比如第一个盒子不选，但是第二个盒子可以放到第一个盒子里面。
然后就转化为最长递增序列的问题了。
1 /* 2 感觉像是变形的最长递增子序列 3 如何快捷的判断一个盒子进过变换能放到另一个盒子里面呢？ 4 */ 5 #include <stdio.h> 6 #include <string.h> 7 #include <algorithm> 8 using namespace std; 9 const int INF = 1<<30; 10 struct node 11 { 12 int minNum; 13 int id; 14 int dimension[10]; 15 bool operator<(const node&rhs)const 16 { 17 return minNum < rhs.minNum; 18 } 19 }a[33]; 20 bool canInput[33][33];//canInput[i][j]判断j能不能放到i里面去 21 int dp[100]; 22 int path[33]; 23 int ans[100]; 24 int main() 25 { 26 27 int n,k,i,j,z; 28 while(scanf("%d%d",&k,&n)!=EOF) 29 { 30 memset(ans,0,sizeof(ans)); 31 memset(canInput,false,sizeof(canInput)); 32 memset(dp,0,sizeof(dp)); 33 for(i=0; i<k; ++i) 34 { 35 dp[i] = 1; 36 path[i] = i; 37 a[i].minNum = INF; 38 a[i].id = i+1; 39 for(j=0; j<n; ++j) 40 { 41 scanf("%d",&a[i].dimension[j]); 42 a[i].minNum = min(a[i].minNum,a[i].dimension[j]); 43 } 44 sort(a[i].dimension,a[i].dimension+n); 45 } 46 47 sort(a,a+k); 48 for(i=0; i<k; ++i)//预处理，判断i能不能放到j里面去 49 for(j=i+1; j<k; ++j) 50 { 51 bool can = true; 52 for(z=0; z<n; ++z) 53 { 54 if(a[i].dimension[z] >= a[j].dimension[z]) 55 can = false; 56 } 57 if(can) 58 canInput[j][i] = true; 59 } 60 //这里就是求最长递增子序列，时间复杂度是O(k*k) 61 for(i=0; i<k; ++i) 62 for(j=0; j<i; ++j) 63 { 64 if(canInput[i][j])//预处理之后，就变成了一维的最长递增子序列的求解了 65 { 66 if(dp[j]+1 >dp[i]) 67 { 68 dp[i] = dp[j]+1; 69 path[i] = j; 70 //break; 这里可不能break， 比如例子：1 2 3 4 5 11 12 13 10 14 71 } 72 } 73 } 74 int cnt = 0,index; 75 for(i=0; i<k; ++i) 76 if(cnt < dp[i]) 77 { 78 cnt = dp[i]; 79 index = i; 80 } 81 82 printf("%d ",cnt); 83 ans[--cnt] = a[index].id; 84 85 while(path[index]!=index) 86 { 87 ans[--cnt] = a[path[index]].id; 88 index = path[index]; 89 } 90 printf("%d",ans[cnt++]); 91 while(ans[cnt]!=0) 92 { 93 printf(" %d",ans[cnt++]); 94 } 95 puts(""); 96 } 97 return 0; 98 }
当然也可以建图（dag图），然后求最长路， 最长路的一种求法就是进行拓扑排序，然后进行最长递增子序列dp， 拓扑排序同上面的排序一样，也是为了消除后效性
然后这种做法，相当于上面，太复杂了。 但是是为了天马行空的想法而A题，而不是为了A题而A题。
1 /* 2 建图（dag图）， 3 拓扑排序 4 dp 5 */ 6 7 #include <stdio.h> 8 #include <string.h> 9 #include <algorithm> 10 #include <stack> 11 using namespace std; 12 const int INF = 1<<30; 13 struct node 14 { 15 int dimension[10]; 16 17 }a[33]; 18 bool canInput[33][33];//canInput[i][j]判断i能不能放到j里面去 19 int dp[100]; 20 int path[33]; 21 int ans[100]; 22 int in[30]; 23 int sequeue[30]; 24 int main() 25 { 26 int n,k,i,j,z; 27 while(scanf("%d%d",&k,&n)!=EOF) 28 { 29 memset(ans,0,sizeof(ans)); 30 memset(canInput,false,sizeof(canInput)); 31 memset(dp,0,sizeof(dp)); 32 memset(in,0,sizeof(in)); 33 for(i=0; i<k; ++i) 34 { 35 dp[i] = 1; 36 path[i] = i; 37 for(j=0; j<n; ++j) 38 { 39 scanf("%d",&a[i].dimension[j]); 40 } 41 sort(a[i].dimension,a[i].dimension+n); 42 } 43 44 for(i=0; i<k; ++i)//预处理，建图 45 for(j=i+1; j<k; ++j) 46 { 47 bool can = true; 48 for(z=0; z<n; ++z) 49 { 50 if(a[i].dimension[z] >= a[j].dimension[z]) 51 can = false; 52 } 53 if(can) 54 canInput[i][j] = true; 55 can = true; 56 for(z=0; z<n; ++z) 57 { 58 if(a[i].dimension[z] <= a[j].dimension[z]) 59 can = false; 60 } 61 if(can) 62 canInput[j][i] = true; 63 64 } 65 //每个结点的入度 66 for(i=0; i<k; ++i) 67 { 68 for(j=0; j<k; ++j) 69 if(canInput[i][j]) 70 in[j]++; 71 } 72 //拓扑排序，sequeue数组存在排序之后的序列 73 for(i=0; i<k; ++i) 74 { 75 for(j=0; in[j]&&j<k; ++j) 76 NULL; 77 in[j] = -1; 78 sequeue[i] = j; 79 for(z=0; z<k; ++z) 80 if(canInput[j][z]) 81 in[z]--; 82 } 83 84 //对拓扑排序之后的序列进行最长递增子序列的dp 85 for(i=0; i<k; ++i) 86 for(j=0; j<i; ++j) 87 { 88 if(canInput[sequeue[j]][sequeue[i]] && dp[j]+1>dp[i])//sequeue[i] 89 { 90 dp[i] = dp[j]+1; 91 path[i] = j; 92 } 93 } 94 int cnt = 0,index; 95 for(i=0; i<k; ++i) 96 if(cnt < dp[i]) 97 { 98 cnt = dp[i]; 99 index = i; 100 } 101 printf("%d ",cnt); 102 103 ans[--cnt] = index; 104 while(path[index] != index) 105 { 106 ans[--cnt] = path[index]; 107 index = path[index]; 108 } 109 //sequeue[i] 110 printf("%d",sequeue[ans[cnt++]]+1); 111 while(ans[cnt]!=0) 112 { 113 printf(" %d",sequeue[ans[cnt++]]+1); 114 } 115 puts(""); 116 } 117 return 0; 118 }