本文共 1469 字，大约阅读时间需要 4 分钟。
题目链接： http://acm.nyist.net/JudgeOnline/problem.php?pid=16
题意描述： 有n个矩形， 定义两个矩形能够嵌套的情况是， 长和宽同时小于另外一个矩形的长和宽或宽和长， 问最多能够嵌套多少个矩形？
解题思路： 设G[i][j] 表示矩形i能不能够嵌套在矩形j中，d[i]表示以矩形i为起点的最长路径。 则状态转移方程为d[i] = max(d[i], dp[j]+1|G[i][j] == 1)， 于是将这个问题转化成了有向图的最长路径问题。
代码：
#include #include #include #include #include #include #include using namespace std;const int MAXN = 1000+7;int G[MAXN][MAXN];struct Node { int x, y;};Node a[MAXN];int d[MAXN];int n;int dp( int i ) { // dp(i) 表示从i号矩形为起点出发的最长路径长度为dp(i) int & ans = d[i]; if( ans > 0 ) return ans; for( int j = 0; j < n; j++ ) { if( G[i][j] ) { ans = max( ans, dp(j)+1 ); } } return ans;}int main() { int T; while( ~scanf( "%d", &T ) ) { while( T-- ) { memset(G, 0, sizeof(G)); memset(a, 0, sizeof(a)); memset(d, 0, sizeof(d)); scanf( "%d", &n ); for( int i = 0; i < n; i++ ) { scanf( "%d%d", &a[i].x, &a[i].y ); } for( int i = 0; i < n; i++ ) { for( int j = 0; j < n; j++ ) { if( (a[i].x < a[j].x && a[i].y < a[j].y) || (a[i].y < a[j].x && a[i].x < a[j].y) ) { G[i][j] = 1; // i------->j } } }// for( int i = 0; i < n; i++ ) {// for( int j = 0; j < n; j++ ) {// cout << G[i][j] << " ";// }// cout << endl;// } int ans = 0; for( int i = 0; i < n; i++ ) { ans = max( ans, dp(i) ); } printf( "%d\n", ans + 1 ); } } return 0;}
思考： 动态规划扔了有一段时间了啊.......
转载于:https://www.cnblogs.com/FriskyPuppy/p/7262780.html
