uva10131 Is Bigger Smarter

keywords: 递归

题目要点：

1. 按照体重排序后，就可以走LIS

2.递归输出路径的方法 3.用记忆化写的时候，需要重新考虑区间的含义。是DAG上的DP问题

循环版本

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

struct node
{
    int idx, w, s;
    node(){}
    node(int a, int b, int c){
        idx = a, w = b, s = c;
    }

    bool operator< (const node& W)const{
        return w < W.w;
    }
};

vector<node> A;
int idx;
vector<int> ans, now;
int maxn = -1, last;
int dp[N];
int path[N];

void print(int u)
{
    //printf("---%d\n", u);
    if (path[u] == u) 
    {
        printf("%d\n", A[u].idx);
        return ;
    }

    print(path[u]);
    printf("%d\n", A[u].idx);
}

int main()
{
    //freopen("1.in", "r", stdin);

    int w, s;
    while (cin >> w >> s){
        idx++;
        A.push_back(node(idx, w, s));
    }

    sort(A.begin(), A.end());

    int len = A.size();
    for (int i = 0; i < len; i++) path[i] = i;

    for (int i = 0; i < len; i++){
        dp[i] = 1;
        for (int j = 0; j < i; j++){
            if (A[j].w < A[i].w && A[j].s > A[i].s && dp[j] + 1 > dp[i]){
                dp[i] = dp[j] + 1;
                path[i] = j;
            }
        }

        if (dp[i] > maxn){
            maxn = dp[i];
            last = i;
        }
    }
    cout << maxn << '\n';
    print(last);

    return 0;
}

记忆化版本

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

struct node
{
    int idx, w, s;
    node(){}
    node(int a, int b, int c){
        idx = a, w = b, s = c;
    }

    bool operator< (const node& W)const{
        return w < W.w;
    }
};

int n;
int maxn = -1;
int mem[N][N];
int g[N][N];
vector<node> A;

int dp(int i, int j)
{
    int &ret = mem[i][j];
    if (ret != -1) return ret;

    for (int k = 0; k < n; k++){
        if (k == j) continue;
        if (g[j][k]){
            ret = max(ret, dp(j, k) + 1);
        }
    }

    if (ret == -1) ret = 2;
    return ret;
}

void print(int i, int j)
{
    cout << i + 1 << '\n';

    if (mem[i][j] == 2){
        cout << j + 1 << '\n';
        return ;    
    }

    for (int k = 0; k < n; k++){
        if (k == j) continue;
        if (g[j][k] && mem[i][j] == mem[j][k] + 1){
            print(j, k);
            break;
        }
    }
}

int main()
{
    //freopen("1.in", "r", stdin);

    int w, s;
    while (cin >> w >> s){
        n++;
        A.push_back(node(n, w, s));
    }

    memset(mem, -1, sizeof mem);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++){
            if (i == j) continue;
            if (A[i].w < A[j].w && A[i].s > A[j].s) g[i][j] = 1;
        }

    int tx, ty;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (g[i][j]){
                int t = dp(i, j);

                if (t > maxn){
                    maxn = t;
                    tx = i, ty = j;
                }
            }

    printf("%d\n", maxn);
    print(tx, ty);
    return 0;
}

这道题目，较少有用递归实现的，故拿来分享。