hdu 1069 dp(最大递增子序列)

//hdu 1069

//dp(最大递增子序列)

//都不懂dp，先做做这种简单的dp

//这题相当于最大递增子序列，按面积递增,

//可以先按面积排序后,两重循环，第一重 i

//表示到第 i 个block 时的最高高度,

//第二重是搜索 i 之前的block 看 i 能否放在其上，

//若可以则记录所有满足条件的 j 中的最高值max，

//则 i 的高度即为自身高度加上 max

//这题每个 block 的三个数据中任意一个都可以当做高，

//所以可以组成三种block。按面积排序时，若从小到大，

//则循环时要 i 能放在 j 上面，若从大到小，则要把 i 放在j的下面

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

#define N 100

struct Recta

{

int x, y, z, area;

}rec[N];

int n_rect, cnt;

int dp[N];

bool cmp(Recta a, Recta b)

{ //按面积从小到大排序

return a.area > b.area;

}

int main()

{

int num[4];

int t = 0;

while(scanf("%d", &n_rect), n_rect)

{

t++;

memset(dp, 0, sizeof(dp));

cnt = 0;

for(int i = 0; i < n_rect; ++i)

{

int x, y, z;

scanf("%d%d%d", &x, &y, &z);

rec[cnt].z = x, rec[cnt].x = y, rec[cnt].y = z, rec[cnt++].area = y * z;

rec[cnt].z = y, rec[cnt].x = x, rec[cnt].y = z, rec[cnt++].area = x * z;

rec[cnt].z = z, rec[cnt].x = x, rec[cnt].y = y, rec[cnt++].area = x * y;

}

//最大递增子序列,跟值大小有关系，要想得到最优值

//就要先排序让其递增

sort(rec, rec + cnt, cmp);

int ans = 0;

dp[0] = rec[0].z;

for(int i = 1; i < cnt; ++i)

{

int max = 0;

for(int j = 0; j < i; ++j)

{ //假定要把i 叠上去，找到高度最大且 i 可以放在上面的 j

if(rec[j].x > rec[i].x && rec[j].y > rec[i].y && dp[j] > max ||

rec[j].y > rec[i].x && rec[j].x > rec[i].y && dp[j] > max)

max = dp[j];

}

dp[i] = max + rec[i].z;

if(dp[i] > ans)

ans = dp[i];

}

printf("Case %d: maximum height = %d\n", t, ans);

}

return 0;

}

posted on 2012-04-11 20:59 gabo 阅读(116) 评论(0) 编辑收藏引用所属分类: dp

只有注册用户登录后才能发表评论。




网站导航: 博客园博客园最新博文博问管理

Blog Stats

文章分类

文章档案

gabo