Uva 437 바빌론 탑 & & UVA10003

밑면이 그 아래 입방체의 길이보다 엄격히 작아야 하며, 최고 상황을 구하면, 돌 한 개를 여러 번 사용할 수 있다
구조체로 돌의 세 가지 방치 상황을 기록하고 면적에 따라 순서를 정한다.
dp[i] = max(dp[i],dp[j] + block[i].hight);i를 선택했을 때 앞의 몇 개와 비교하여 현재 상황에서 가장 높은 가능성을 찾아내다
 
 

<span style="font-size:18px;">#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

struct node
{
    int x;
    int y;
    int hight;
}block[100];
int dp[100];
bool cmp(node a,node b)
{
    return a.x*a.y < b.x*b.y;
}

int main()
{
    int n,a,b,c,cas = 1;
    while(scanf("%d",&n) && n)
    {
        int tmp = 1;
        for(int i = 0;i < n;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            block[tmp].x = a;
            block[tmp].y = b;
            block[tmp++].hight = c;
            block[tmp].x = c;
            block[tmp].y = a;
            block[tmp++].hight = b;
            block[tmp].x = b;
            block[tmp].y = c;
            block[tmp++].hight = a;
        }
        sort(block+1,block+tmp,cmp);
        memset(dp,0,sizeof(dp));
        for(int i = 1;i < tmp;i++)
        {
            dp[i] = block[i].hight;
            for(int j = 1;j < i;j++)
            {
                if(((block[i].x>block[j].x)&&(block[i].y>block[j].y))||((block[i].x>block[j].y)&&(block[i].y>block[j].x)))
                    dp[i] = max(dp[i],dp[j] + block[i].hight);
            }
        }
        int maxn=0;
        for(int i = 1;i < tmp;i++)
            if(dp[i] > maxn)
                maxn = dp[i];
        printf("Case %d: maximum height = %d
",cas++,maxn);
    }
    return 0;
}</span>

길이가 10미터인 나무 막대기는 반드시 2, 4, 7미터의 곳에서 절단해야 한다.이럴 땐 몇 가지 선택이 있어.너는 먼저 2미터를 자른 다음에 4미터를 자른 다음에 마지막에 7미터를 자른 곳을 선택할 수 있다.이러한 선택의 비용은 10+8+6=24이다.처음 자를 때는 막대기 길이가 10m, 두 번째 자를 때는 막대기 길이가 8m, 세 번째 자를 때는 막대기 길이가 6m였기 때문이다.그러나 만약에 네가 먼저 4미터를 자른 다음에 2미터를 자른 곳, 마지막으로 7미터를 자른 곳을 선택한다면 그 원가는 10+4+6=20이다. 이 원가가 비교적 좋은 선택이다.
너의 사장은 너의 컴퓨터 능력이 반드시 나무 막대기를 자르는 데 필요한 최소한의 비용을 찾아낼 수 있을 것이라고 믿는다.
p[j]-p[i]는 첫 번째 칼의 비용을 대표하며, 잘라서 i~k와 k~j 두 부분으로 바꿉니다.

#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAX 0x3f3f3f3f

using namespace std;

int len;
int d[50][50];
int p[51];

int main()
{
    int n;
    while(scanf("%d",&n) && n)
    {
        int m;
        scanf("%d",&m);
        for(int i=1; i <= m; i++)
            scanf("%d",&p[i]);
        p[0] = 0,p[m+1] = n;
        memset(d,0,sizeof(d));

        for(int l = 2; l <= m+1; l++)
            for(int i = 0; i + l <= m+1; i++)
            {
                int j = i + l;
                d[i][j] = MAX;
                for(int k = i+1; k < j; k++)
                {
                    d[i][j] = min(d[i][j],d[i][k]+d[k][j]+p[j]-p[i]);
                }
            }
        printf("The minimum cutting is ");
        printf("%d.
",d[0][m+1]);
    }
    return 0;
}