poj 2241 단순 dp (최고 바빌론 타 워)
1147 단어 동적 계획 - 1D / 1D
사고: 모든 입방체 를 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