poj 2241 단순 dp (최고 바빌론 타 워)

제목: 현재 30 개 를 넘 지 않 는 입방체 가 있다.가장자리 길이 지정: a * b * c.각 입방체 의 개 수 는 제한 이 없다 는 것 을 이미 알 고 있다.지금 입방체 를 쌓 으 려 면 두 입방체 가 쌓 을 수 있 는 조건 은 위의 입방체 의 밑면 길이 와 너비 가 그 아래 에 놓 인 입방체 보다 엄 격 히 작 다 는 것 이다.이 입방체 들 이 가장 높이 쌓 일 수 있 는 지 물 었 다.
사고: 모든 입방체 를 abc 의 배열 에 따라 6 개의 입방체 로 보고 ab 는 바닥 의 길이 와 너비, c 를 높 게 본다.정렬이후 dp [i] 는 i 번 째 입방체 를 바닥 에 쌓 을 수 있 는 최고 높이 로 표시 했다.
#include 
#include 
#include 
#define Max(a,b) ((a)>(b)?(a):(b))
#define N 185
struct node{
	int a,b,h;
}p[N];
int dp[N],n,C=1;
int cmp(const struct node *a,const struct node *b){
	if((*a).a == (*b).a)
		return (*a).b - (*b).b;
	return (*a).a - (*b).a;
}
int main(){
	freopen("a.txt","r",stdin);
	while(scanf("%d",&n) && n){
		int i,j,a,b,c,top,res;
		top = res = 0;
		for(i = 0;i=0;j--)
				if(p[i].a > p[j].a && p[i].b > p[j].b)
					dp[i] = Max(dp[i],dp[j]+p[i].h);
		for(i = 0;i

좋은 웹페이지 즐겨찾기