uva 103 - Stacking Boxes

題目意思：   給定n個m維的矩形，問我們能夠嵌套的矩形最多有幾個，輸出個數和嵌套的矩形編號

解題思路：   1 DP 最長上升子序列（矩形嵌套的變形）
                     2  由於維數最多有10，那麼必須用結構體存儲，其它和二維的是一樣的，注意結構體的排序，路徑記錄等

聲明：          這個代碼在uva AC了，可是在hdu 1614WA了，搞了很久實在找不到原因，知道的大牛請弱弱的說一下，小弟不勝感激

代碼：
[cpp] 
#include <algorithm> 
#include <iostream> 
#include <cstring> 
#include <string> 
#include <vector> 
#include <cstdio> 
#include <stack> 
#include <queue> 
#include <set> 
using namespace std; 
#define MAXN 50 
 
struct Box{ 
    int dimen[10]; 
}s[MAXN]; 
int n , m , max_len , pos; 
int dp[MAXN]; 
int path[MAXN][MAXN]; 
int num[MAXN]; 
 
//自定義cmp函數 
bool cmp(int a , int b){ 
    return a>b?true:false; 
} 
 
//判斷函數 
inline int judge(Box b1 , Box b2){ 
    for(int i = 0 ; i < m ; i++){ 
        if(b1.dimen[i] <= b2.dimen[i]) return 0;//相等也是不滿足 
    } 
    return 1; 
} 
 
//求解最長上升子序列 
inline void solve(){ 
    Box tmp_s[MAXN]; 
    int vis[MAXN] , tmp[MAXN]; 
    memset(vis , 0 , sizeof(vis)); 
    memset(dp , 0 , sizeof(dp));  
    memset(num , 0 , sizeof(num));  
    memset(path , 0 , sizeof(path)); 
    //排序從新賦值 
    for(int i = 0 ; i < n ; i++) 
        tmp[i] = s[i].dimen[0]; 
    sort(tmp , tmp+n); 
    for(int i = 0 ; i < n ; i++){ 
        for(int j = 0 ; j < n ; j++){ 
            if(tmp[i] == s[j].dimen[0] && !vis[j]){ 
               tmp_s[i] = s[j] ; num[i] = j+1; 
               vis[j] = 1 ; break;    
            } 
        } 
    } 
     
    max_len = 1 ; dp[0] = 1 ; //初始化 
    path[0][0] = num[0] ; pos = 0; //初始化，pos記錄max_len是在哪個位置 
    for(int i = 1 ; i < n ; i++){ 
        dp[i] = 1 ; path[i][0] = num[i];//初始化 
        for(int j = i-1 ; j >= 0 ; j--){ 
            if(judge(tmp_s[i] , tmp_s[j]) && dp[j]+1 > dp[i]){//如果有更新dp[i]，就要更新path[i] 
                dp[i] = dp[j] + 1; 
                memcpy(path[i] , path[j] , sizeof(path[j])); 
                for(int k = 0 ; ; k++){ 
                    if(!path[i][k]){ path[i][k] = num[i] ; break;}//把num[i]插入path[i]後面 
                } 
            } 
            if(max_len < dp[i]){ //更新max_len 
                max_len = dp[i] ; pos = i; 
            } 
        } 
    } 
} 
 
//輸出 
inline void output(){ 
    printf("%d\n%d" , max_len , path[pos][0]); 
    for(int i = 1 ; i < max_len ; i++) 
        printf(" %d" , path[pos][i]); 
    printf("\n"); 
} 
 
//主函數 
int main(){ 
    //freopen("input.txt" , "r" , stdin); 
    int tmp[MAXN]; 
    while(scanf("%d" , &n) != EOF){ 
        scanf("%d" , &m); 
        for(int i = 0 ; i < n ; i++){ 
            for(int j = 0 ; j < m ; j++) 
                scanf("%d" , &tmp[j]); 
            sort(tmp , tmp+m , cmp); 
            for(int j = 0 ; j < m ; j++) 
                s[i].dimen[j] = tmp[j]; 
        } 
        solve() ; output(); 
    } 
    return 0; 
}