#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\n",cas++,maxn);

    }

    return 0;

}</span>

有一根长10公尺的木棍必须在第2、4、7公尺的地方切割。这个时候就有几种选择了。你可以选择先切2公尺的地方，然后切4公尺的地方，最后切7公尺的地方。这样的选择其成本为：10+8+6=24。因为第一次切时木棍长10公尺，第二次切时木棍长8公尺，第三次切时木棍长6公尺。但是如果你选择先切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.\n",d[0][m+1]);

    }

    return 0;

}