UVA 103 Stacking Boxes (DP)

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;
}