hdu 1160 정렬 + 최장 상승 서열

제목:

수출 체중이 상승하고 속도가 떨어지는 최장자 서열

제목:

먼저 구조체의 상승 순서에 따라 체중을 정렬한 다음에 dp로 속도에 대한 최장 하강 서열을 구하면 된다.

코드:

#include <set>
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long int LL;
const int M = 1009,INF = 0x3fffffff;
struct place {int x, y, z;} a[M];
pair<int, int> dp[M];
bool cmp(struct place a, struct place b) {
    if(a.x == b.x) return a.y > b.y;
    if(a.x < b.x) return true;
    return false;
}

int main(void) {
    //problem:hdu 1160 address:http://acm.hdu.edu.cn/showproblem.php?pid=1160
    int n = 0;
    while(cin >> a[n].x >> a[n].y) {
        a[n].z = n + 1;
        n++;
    }
    sort(a, a + n, cmp);
    //for(int i = 0; i < n; i++) cout << a[i].x << " " << a[i].y << " " << a[i].z << endl;
    for(int i = 0; i < n; i++) dp[i].first = 1;
    int ans = 0, key = 0;
    for(int i = 0; i < n; i++) {
        for(int j = i - 1; j >= 0; j--) {
            if(a[i].x != a[j].x && a[i].y < a[j].y && dp[i].first < dp[j].first + 1) {
                dp[i].second = j;
                dp[i].first = dp[j].first + 1;
            }
        }
        //for(int ii = 0; ii < n; ii++) cout << dp[ii].first << " " << dp[ii].second << " ";
        //cout << endl;
        if(ans <= dp[i].first) {key = i; ans = dp[i].first;}
    }
    cout << ans << endl;
    stack<int> s;
    while(ans--) {
        s.push(a[key].z);
        key = dp[key].second;
    }
    while(!s.empty()) {
        cout << s.top() << endl;
        s.pop();
    }
    return 0;
}