题目链接： https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=378
题目描述： n种无限量的石块， 摞起来， 要求只能同时小于时嵌套， 问最大高度是多少
解题思路： 完全是嵌套矩形啊
代码：
#include <iostream> #include <cstdio> #include <string> #include <vector> #include <map> #include <cstring> #include <iterator> using namespace std; struct Node { int x; int y; int z; Node() { x = y = z = 0; } Node( int _x, int _y, int _z ) { x = _x; y = _y; z = _z; } void just( int _x, int _y, int _z ) { x = _x; y = _y; z = _z; } }; Node arr[200]; int dp[200]; // dp[i]以i号为最上面的石块的最高高度 int vis[200]; // 是否被访问过 int ok( int i, int j ) { // i号是否可以放在j号的上面 if( arr[i].x < arr[j].x && arr[i].y < arr[j].y ) return 1; return 0; } int cnt; int solve( int i ) { if( vis[i] ) return dp[i]; for( int j = 0; j < cnt; j++ ) { if( ok( i, j ) ) { vis[i] = 1; dp[i] = max( dp[i], solve(j)+arr[i].z ); } } return dp[i]; } int main() { int n; int cases = 1; while( ~scanf( "%d", &n ) && n ) { memset(arr, 0, sizeof(arr)); memset(dp, 0, sizeof(dp)); memset(vis, 0, sizeof(vis)); cnt = 0; while( n-- ) { int a, b, c; scanf( "%d%d%d", &a, &b, &c ); arr[cnt++].just(a, b, c); arr[cnt++].just(a, c, b); arr[cnt++].just(b, a, c); arr[cnt++].just(b, c, a); arr[cnt++].just(c, a, b); arr[cnt++].just(c, b, a); } for( int i = 0; i < cnt; i++ ) { dp[i] = arr[i].z; } // for( int i = 0; i < cnt; i++ ) { // cout << arr[i].x << " " << arr[i].y << " " << arr[i].z << endl; // } // for( int i = 0; i < cnt; i++ ) { // cout << dp[i] << " "; // } // cout << endl; int ans = -1; for( int i = 0; i < cnt; i++ ) { ans = max( ans, solve(i) ); } printf( "Case %d: maximum height = %d ", cases++, ans ); } return 0; }
思考： 这个是以前做过的题， 然后数组实现方法没写出来......看看别人怎么写的哈
大家都写得是函数， 个人觉得原因是无法没有确定的边缘值， 所以与其说这是DP， 不如说这是一种记忆化的搜索， DP必须要有边缘值的