uva 10131 - Is Bigger Smarter?

題目意思：     有一群大象，大象有兩個參數就是體重和IQ，現在要在這些大象裡面找到最多的n只，使得有體重  W[a[1]] < W[a[2]] < ... < W[a[n]] ， 和 IQ S[a[1]] > S[a[2]] > ... > S[a[n]]，找到這個n 並且輸出對應的編號

解題思路：     1:最長上升子序列（只是限制條件裡面多了一個s是要嚴格遞減的）
                      2：我們可以先對IQ這一列先排序，對應的體重也要先應的變化，然後我們按照求解最長上升子序列的方法求解，就是在這個過程我麼要去判斷後面的IQ肯定要比前面的小才能夠滿足。由於這一題還要求輸出路徑，那麼我們一般都是在狀態轉移的記錄路徑的，具體見一下的代碼

代碼：
[cpp] 
#include <algorithm> 
#include <iostream> 
#include <cstring> 
#include <string> 
#include <vector> 
#include <cstdio> 
#include <stack> 
#include <queue> 
#include <cmath> 
using namespace std; 
#define MAXN 1010 
 
int w[MAXN] , s[MAXN];//保存輸入 
int tmp_w[MAXN] , tmp_s[MAXN];//保存排序後的結果 
int num[MAXN] , path[MAXN][MAXN] , vis[MAXN];//num記錄編號，path記錄路徑，vis用做標記 
int dp[MAXN];//每一個對應的最長的上升子序列的長度 
int len , max_path , pos; 
 
//自定義cmp函數(注意函數的形式) 
bool cmp(int a , int b){ 
    return a>b?true:false; 
} 
 
void solve(){ 
    int  i , j; 
    memset(vis , 0 ,sizeof(vis)); 
    memcpy(tmp_s , s , sizeof(tmp_s)); 
    sort(tmp_s , tmp_s+len , cmp); 
    for(i = 0 ; i < len ; i++){ 
        for(j = 0 ; j < len ; j++){ 
            if(tmp_s[i] == s[j] && !vis[j]){ 
                tmp_w[i] = w[j];  
                vis[j] = 1 ; num[i] = j+1; 
                break; 
            } 
        } 
    } 
    //求解最長公共子序列+路徑記錄 
    memset(dp , 0 , sizeof(dp)); 
    dp[0] = 1 ; max_path = 1 ; path[0][max_path-1] = num[0]; pos = 0; 
    for(i = 1 ; i < len ; i++){ 
        dp[i] = 1 ; path[i][0] = num[i];//初始化 
        for(j = i-1 ; j >= 0 ; j--){ 
            if(tmp_w[i] > tmp_w[j] && tmp_s[i] < tmp_s[j]){ 
                if(dp[j] + 1 > dp[i]) {//更新了dp[i],就要更新path[i] 
                    dp[i] = dp[j] + 1; 
                    memcpy(path[i] , path[j] , sizeof(path[j])); 
                    path[i][dp[i]-1] = num[i]; 
                } 
                if(max_path < dp[i]) {//更新了max_path，記錄最大的位置pos 
                   max_path = dp[i] ; pos = i; 
                } 
            } 
        } 
    } 
    //輸出 
    printf("%d\n" , max_path); 
    for(i = 0 ; i < max_path ; i++) printf("%d\n" , path[pos][i]); 
} 
 
int main(){ 
    //freopen("input.txt" , "r" , stdin); 
    int n , m , i = 0; www.2cto.com
    while(cin>>n>>m){ 
        w[i] = n ; s[i] = m ; i++; 
    } 
    len = i ; solve(); 
    return 0; 
}