首页 > 其他 > 详细

uva 10131 Is Bigger Smarter? (DAG)

时间:2015-03-14 18:34:41      阅读:354      评论:0      收藏:0      [点我收藏+]

uva 10131 Is Bigger Smarter?

题目大意:当一只大象的体重大于另一只的体重,且智商小于另一只的智商,该大象便可以“嵌套”另一只大象。问,最长的嵌套方式。(答案不唯一)

解题思路:DAG。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
struct ELE{
    int w, i;
};
ELE e[10005];
int dp[10005], cnt, rec[10005];;

int check(int a, int b) {
    if (e[a].w > e[b].w && e[a].i < e[b].i) return 1;
    else return 0;
}

int DP(int x) {
    if (dp[x]) return dp[x];
    for (int i = 0; i < cnt; i++) {
        if (check(i, x)) {
            int temp = DP(i);
            if (temp > dp[x]) {
                dp[x] = temp;
                rec[x] = i;
            }
        }
    }
    return ++dp[x];
}

void solve() {
    int Max = 0, r;
    for (int i = 0; i < cnt; i++) {
        if (DP(i) > Max) {
            r = i;
            Max = DP(i);
        }
    }
    printf("%d\n", Max);

    for (int i = 0; i < Max; i++) {
        printf("%d\n", r + 1);
        r = rec[r];
    }
}
int main() {
    cnt = 0;
    while (scanf("%d %d", &e[cnt].w, &e[cnt].i) == 2) {
        cnt++;
    }
    memset(dp, 0, sizeof(dp));
    memset(rec, 0, sizeof(rec));
    solve();
    return 0;
}

uva 10131 Is Bigger Smarter? (DAG)

原文:http://blog.csdn.net/llx523113241/article/details/44261453

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!