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.zzzyk.com
    while(cin>>n>>m){
        w[i] = n ; s[i] = m ; i++;
    }
    len = i ; solve();
    return 0;
}

作者：cgl1079743846

补充：软件开发 , C++ ,