Uva 10003，切木棍

题目链接：https://uva.onlinejudge.org/external/100/10003.pdf

题意： L长的木棍，给n个切割点，切成n+1部分，每次切割的时候的费用等于切割时的长度。求最少费用。

这个题目和最优矩阵链乘一样，DP方向既不是顺序，也不是逆序，而是，较大部分状态取决于小部分状态的决策。

d(i,j) 切 i 和 j 的最少费用，那么方程就是 d(i,j) = min(d(i,k)+d(k,j)+a[j]-a[i]);(a[j]-a[i])就是切 i~j的费用。

顺便说一下最优矩阵链乘， n*m 的矩阵 和 m*p 的矩阵，相乘的次数是 n*m*p，矩阵链乘满足结合律，最优矩阵链乘的状态转移方程就是  f(i,j) = min(f(i,k)+f(k+1,j)+p_i-1*p_k*p_j);

切木棍问题也可以用哈夫曼数来做，之前的一篇博客中有写。

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

#define maxn 55
#define INF 0x3f3f3f3f
int a[maxn],vis[maxn][maxn],d[maxn][maxn];

int L,n;

int dp(int i,int j)
{
    if(i>=j-1) return 0;
    if(vis[i][j]) return d[i][j];
    vis[i][j] = 1;

    int & ans = d[i][j];
    for(int k=1; k<=j-1; k++)
        ans = min(ans,dp(i,k)+dp(k,j)+a[j]-a[i]);
    return ans;
}

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

        int ans = dp(0,n+1);
        printf("The minimum cutting is %d.
",ans);

    }

    return 0;
}