UVA 103 Stacking Boxes
看到了这个题之后思路就无比清晰。矩形嵌套问题,不过这个是多维的。我们判断两个序列a,b的关系的时候,需要枚举a的各种排列,看看有没有可能a的每一个位置上的元素都比b中对应元素小,如果真枚举的话太麻烦了。可以把a和b都排下序,然后再比较。确定元素间的关系之后,就很好构造LIS了。在这道题中,我学会了sort和max_element的用法。。感觉stl挺方便的。
#include<iostream> #include<string> #include<cstdlib> #include<algorithm> #include<cstdio> #define M 30 using namespace std; int N,B,flag[30],before[30]; struct node { int a[10]; int order; }; node box[ M ]; bool cmp1(const node a,const node b) { for(int i = 0; i < N; i++ ) if( a.a[i] < b.a[i] ) return true; else if( a.a[i] > b.a[i] ) return false; return false; } int cmp2( int *a,int *b){ for( int i = 0; i < N; i++ ) if( a[i] >= b[i] ) return 0; return 1; } void out( int start,int ceng ) { if( start == -1 ) return; out( before[start],ceng+1 ); cout << box[start].order + 1 ; if( ceng ) cout << ' '; } int main(void) { int i,j,ntemp,be,start,max; while( cin >> B >> N ) { for( i = 0; i < B; i++ ){ for( j = 0; j < N; j++ ) cin >> box[i].a[j]; box[i].order = i; sort( box[i].a,box[i].a+N );//对序列中元素进行排序 } sort( box,box+B ,cmp1);//对所有序列排序 fill( flag,flag+30,0); flag[0] = 1;before[0] = -1; for( i = 1; i < B; i++ ) { ntemp = 0;be = -1; for( j = 0; j < i; j++ ) if( flag[j] > ntemp && cmp2(box[j].a,box[i].a) ) ntemp = flag[be = j]; flag[i] = ntemp + 1; before[i] = be; } start = max_element(flag,flag+B) - flag; max = flag[start] ; cout << max << endl; out( start,0 );//递归输出 cout << endl; } return 0; }