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

 

作者：cgl1079743846