学步园

题意：

要将一段木头的n(n<50)个位置切开。切开花费为所切木头长度的长度。问切完这n个地方的最小花费。

思路：

可以逆向思维。将木头合成一整段。合并花费为合并后的长度。所以可以很快得到O(n^3)的算法。对于n比较小来说完全够用了。dp[i][j]表示合并完[i,j]的最小花费。dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])。k€(i,j)。

详细见代码：

#include<algorithm>
#include<iostream>
#include<string.h>
#include<sstream>
#include<stdio.h>
#include<math.h>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
//#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const double PI=acos(-1.0);
const int maxn=100010;
//typedef __int64 ll;
int dp[100][100],pos[100];
int main()
{
    int l,n,i,len,k;

    while(scanf("%d",&l),l)
    {
        scanf("%d",&n);
        memset(dp,0x3f,sizeof dp);
        pos[0]=0;
        for(i=1;i<=n;i++)
            scanf("%d",&pos[i]);
        n++;
        pos[n]=l;//增加第n段
        for(i=1;i<=n;i++)
            dp[i][i]=0;
        for(len=2;len<=n;len++)//从小段推大段
            for(i=1;i<=n+1-len;i++)
            {
                for(k=i;k<i+len-1;k++)
                    dp[i][i+len-1]=min(dp[i][i+len-1],dp[i][k]+dp[k+1][i+len-1]);
                dp[i][i+len-1]+=pos[i+len-1]-pos[i-1];
            }
        printf("The minimum cutting is %d.\n",dp[1][n]);
    }
    return 0;
}