uva 10003——Cutting Sticks

題意：給定一長為L的木棍和n個切割點，每次切割的費用為切割的長度，求最小的費用。

思路：dp,子問題是區間（i，j）的最小費用，臨界是（i,j)隻有一個切割點。dp[i,j]=min(dp[i,k]+dp[k,j])（k為枚舉切割點）+a[j]-a[i]（第一刀）,3次方的算法。還可以用四邊形不等式優化到平方的算法。

code：

#include <bits/stdc++.h>
using namespace std;

#define ft(i,s,t) for (int i=s;i<=t;i++)
#define cls(v,c) memset(v,c,sizeof(v))
const int N=55;
const int INF=0x3f3f3f3f;

int a[N],dp[N][N];
int main()
{
    int l,n;
    while (~scanf("%d",&l),l)
    {
        cls(dp,INF);
        scanf("%d",&n);a[0]=0,a[n+1]=l;
        ft(i,1,n) scanf("%d",&a[i]);

        ft(i,1,n+1) dp[i-1][i]=0; //no cut point

        ft(i,2,n+1) ft(j,0,n+1-i) ft(k,j+1,j+i-1)
        dp[j][j+i]=min(dp[j][j+i],dp[j][k]+dp[k][j+i]+a[j+i]-a[j]); //cut

        printf("The minimum cutting is %d.\n",dp[0][n+1]);

    }
}