uva 10003 - - Cutting Sticks

题目意思：有一根长度为l的木棍，木棍上面有m个切割点，每一次切割都要付出当前木棍长度的代价，问怎样切割有最小代价

解题思路： 1 区间DP

2 区间动态规划问题一般都是考虑，对于每段区间，他们的最优值都是由几段更小区间的最优值得到，是分治思想的一种应用，将一个区间问题不断划分为更小的区间直至一个元素组成的区间，枚举他们的组合，求合并后的最优值。
3 设F[i,j]（1<=i<=j<=n）表示区间[i,j]内的数字相加的最小代价，最小区间F[i,i]=0（一个数字无法合并，∴代价为0）每次用变量k（i<=k<=j-1）将区间分为[i,k]和[k+1,j]两段

                 4《区间DP模板，代码》
                     for(intp = 1 ; p <= n ; p++){//p是区间的长度，作为阶段
                         for(int i = 1 ; i <= n ; i++){//i是穷举区间的起点
                              int j = i+p-1;//j为区间的终点
                             for(int k = i ; k < j ; k++)//状态转移
                                 dp[i][j] = min{dp[i][k]+dp[k+1][j]+w[i][j]};//这个是看题目意思，有的是要从k开始不是k+1

dp[i][j]= max{dp[i][k]+dp[k+1][j]+w[i][j]};

}
}

5 对于这一题，如果我们只对最左边的切割点到最右边的切割点进行DP，那么得到的答案肯定是错的，因为不是整个区间，所以我们必须在木棍的做左边和左右边分别增加一个点，那么得到的就是整个区间，再对这个区间进行DP求解即可

代码：

[cpp]
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <set>
using namespace std;
#define MAXN 55

int len , m;
int dp[MAXN][MAXN];
int cut[MAXN];//记录切割点

void solve(){
    int i , j , k , p , tmp , min;
    cut[0] = 0 ; cut[m+1] = len;//增加切点，那么切点有0-m+1
    memset(dp , 0 , sizeof(dp));
    for(p = 1 ; p <= m+1 ; p++){//区间长度0-m+1
        for(i = 0 ; i <= m+1-p ; i++){//区间起点0-m+1-p
            j = i+p ; min = 999999999;//j为终点
            for(k = i+1 ; k < j ; k++){//枚举k
                tmp = dp[i][k]+dp[k][j]+cut[j]-cut[i];//这个地方注意不是从k+1开始
                if(tmp < min) min = tmp;//更新min
            }
            if(min != 999999999) dp[i][j] = min;//如果min有更新过则赋值给dp[i][j]
        }
    } www.zzzyk.com
    printf("The minimum cutting is %d.\n" , dp[0][m+1]);//答案就是0-m+1这个区间
}

int main(){
    //freopen("input.txt" , "r" , stdin);
    while(scanf("%d" , &len) && len){
        scanf("%d" , &m);
        for(int i = 1 ; i <= m ; i++) scanf("%d" , &cut[i]);
        solve();
    }
    return 0;
}

作者：cgl1079743846

补充：软件开发 , C++ ,