uva 10131 Is Bigger Smarter? （DAG）

uva 10131 Is Bigger Smarter?题目大意：当一只大象的体重大于另一只的体重，且智商小于另一只的智商，，该大象便可以“嵌套”另一只大象。问，最长的嵌套方式。（答案不唯一）解题思路：DAG。;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;;}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;}

一定要成为你工作最大的资产。