UVA - 103 Stacking Boxes

本文主要是介绍UVA - 103 Stacking Boxes，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：n维向量，如果向量A，B每一位上的数A都比B大，则A可以嵌套住B,求最大的嵌套个数，并输出依次是第几个。

思路：构成一个有向图DAG，如果X可以嵌套在Y里，那么X到Y就有一个有向边，最后就是求DAG上的最长路径

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;int G[32][32],arr[32][32],d[32],n,k,Max;
bool sign;bool isBigger(int a,int b){for (int i = 0; i < k; i++)if (arr[a][i] <= arr[b][i])return false;return true;
}int dp(int i){if (d[i] != -1)return d[i];int &ans = d[i] = 1;   //注意d[i]也要不断的更新for (int j = 0; j < n; j++)if (G[i][j])ans = max(ans,dp(j)+1);return ans;
}void print(int i){if (sign)printf(" %d",i+1);else {printf("%d",i+1);sign = true;}for (int j = 0; j < n; j++)if (G[i][j] && d[j]+1 == d[i]){print(j);break;}
}int main(){while (scanf("%d%d",&n,&k) != EOF){for (int i = 0; i < n; i++){for (int j = 0; j < k; j++)scanf("%d",&arr[i][j]);sort(arr[i],arr[i]+k);}memset(G,0,sizeof(G));for (int i = 0; i < n-1; i++)for (int j = 0; j < n; j++)if (isBigger(j,i))G[i][j] = 1;else if (isBigger(i,j))G[j][i] = 1;memset(d,-1,sizeof(d));int ans = -1,pos;for (int i = 0; i < n; i++){int t = dp(i);if (t > ans){ans = t;pos = i;}}printf("%d\n",ans);sign = false;print(pos);printf("\n");}return 0;
}

这篇关于UVA - 103 Stacking Boxes的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---