UVa 437 The Tower of Babylon

好久不水

开始深入算法了。


题目传送门


题目其实很简单,暴搜都可以,网上最多的解法都是记忆化搜索,效率应该不差。

不过对于一个迷恋上DP的人,又怎么愿意去干搜索这种体力活。


原归正转,先看题目数量无限,但是想一下就知道每种物品最多就3个,所以把所有物品拆成3n个,

然后觉得跟LIS是一样的,所以就来了两重循环。


for ( int i(1); i<=n; i++) {
	d[i] = a[i].c;
	for ( int j(1); j<i; j++) {
		if (a[j].a<a[i].a && a[j].b<a[i].b && d[j]+a[i].c>d[i]){
			d[i] = d[j] + a[i].c;
		}
	}
	ans = max(ans, d[i]);
}


出来之后发现不对。仔细想想发现跟LIS不一样,因为无序,会出现ACB这样的情况。


怎么办呢?

靠直觉我又把上面的循环走了n次。。


for ( int k(1); k<=n; k++){
	for ( int i(1); i<=n; i++){
		for ( int j(1); j<=n; j++) if (a[j].a>a[i].a && a[j].b>a[i].b && d[j]+a[i].c>d[i] ){
			d[i] = d[j]+a[i].c;
		}
	}
}

AC确实没问题了,关键是复杂度抬高了一个数量级!


再仔细想想发现原来真的是想多了。回到刚刚说的问题,仿LIS主要的问题是会出现ACB的情况,按照题意,既然出现了ACB,便不再会有ABC的情况。这样的话,我只需要排个序,把C放在B前面即可,排序条件当然是按底面积。


最后代码如下:


#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
using namespace std;

const int INF = 0x3fffffff;
const double eps = 1e-6;

struct NODE{
	int a,b,c;
	NODE(){}
	NODE(int x,int y,int z): a(x),b(y),c(z) {}
}a[111];

bool cmp(NODE a,NODE b){
	if (a.a==b.a) return a.b<b.b;
	return a.a<b.a;
}
int d[111];

int I,T,n,m;

int main(){
	freopen("in.txt","r",stdin);
	while ( scanf("%d",&n) && n){
		for ( int i(0); i<n; i++) {
			int a1,b1,c1;
			scanf("%d%d%d",&a1, &b1, &c1);
			if (b1<a1) swap(a1,b1);
			if (c1<b1) swap(b1,c1);
			if (b1<a1) swap(a1,b1);
			// printf("%d,%d,%d\n",a1,b1,c1);
			a[i*3+1]=NODE(a1,b1,c1);
			a[i*3+2]=NODE(a1,c1,b1);
			a[i*3+3]=NODE(b1,c1,a1);
		}
		n*=3;
		sort(a+1,a+n+1,cmp);
		memset(d, 0, sizeof(d));
		int ans = 0;
		for ( int i(1); i<=n; i++) {
			d[i] = a[i].c;
			for ( int j(1); j<i; j++) {
				if (a[j].a<a[i].a && a[j].b<a[i].b && d[j]+a[i].c>d[i]){
					d[i] = d[j] + a[i].c;
				}
			}
			ans = max(ans, d[i]);
		}
			
		printf("Case %d: maximum height = %d\n", ++I, ans);
	}
	return 0;
}


看最后的思路,时不时一下透亮了许多。

感叹果然DP大法神。

就是要非常理解方程背后的道理。这个才真的有价值!



注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
2022-12-10 18:47
门头沟学院_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议