UVa10003(切木棍)题解

题目理解

题目大意是给你一根木棍，棍子上有n个切割点，,要求将木棍分成n+1个部分，每次切割的费用是木棍的长度，输入是木棍的长度和切割点的个数(当木棍长度为0时程序退出，否则程序一直运行),输出是最小的总切割费用。

解题思路

这里我们用动态规划的思想解决这道题目，动态规划的关键就是要定义好状态，并找出状态转移方程，这里我们定义dp[i][j]表示切割点i到j这根子木棍所需的最小花费.

最后一步

在使用上述状态的情况下，dp的最后一步就是计算i=0,j=n+1时的花费(注意，i和j表示的是切割点的标号，而明显之前输入1-n个切割点时是不会包括木棍的两端的，所以这两个点的值要自己设置好).那么这最后一步如何计算呢?举一个例子.

这里木棍的长度为10，输入了两个切割点，加上两个端点，一共四个点，节点标号分别为0,1,2,3,dp[0][3]怎么计算呢?这根木棍一共两种切割方式，一种以3为切割点，一种以6为切割点,分别的总花费是10+7和10+6，写成另一种形式为dp[0][3]=dp[0][2]+dp[2][3]或者dp[0][4]=dp[0][1]+dp[1][3]，而dp[2][3]和dp[0][1]显然都是0，那么关键就在于计算出dp[0][2]和dp[1][3]，由对最后一步的分析，我们可以这个问题可以分解成哪些子问题进行求解.

重叠子问题

由之前的分析得到，要想求出整根木棍的切割费用，我们可以先求出短一点的木棍的最小费用，而最短的木棍不就是中间没有切割点的木棍吗？如果不使用数组来储存小木棍的最小费用，就会发生重复计算。我们小木棍计算起，当考虑木棍之间有一个切割点时，比如dp[0][2]，我们计算了一遍，等到我们计算木棍间有两个切割点时，比如dp[0][3]，dp[0][3]=dp[0][2]+dp[2][3]，我们又计算了一遍。从对重叠子问题的分析中，我们可以知道dp数组储存的是什么内容，用途在于何处。

状态转移方程

由上述分析可知，切割一根木棍的最小花费取决于此时木棍的长度以及木棍可以被分割为哪些子木棍，不难得到状态转移方程。

dp[j][i] = min(dp[j][i], dp[j][k] + dp[k][i] + place[i] - place[j]);

其中k取遍i到j的所有值.

边界处理

由于一根木棍如果中间没有切割点的话，他的花费是0，这里我们需要编写代码进行初始化。

for (int i = 0; i <= dots; i++)
{
    dp[i][i+1] = 0;
}

递推顺序

由于在计算最后一次状态值前，必须满足之前的状态全都被计算过，并且已经达到最优状态.所以，我们第一层循环从小到大枚举所有切割点，但是由于线段是有两个点的，所以我们需要第二层循环，如果两层循环都是从小到大枚举，那么最后一个步骤必定是dp[length][length],例如木棍的长度为10，假设代码如下:

for(int i=0;i<length;i++)
{
    for(int j=0;j<length;j++){
    dp[i][j]=状态转移方程;}
}

很明显，for循环结束时绝对不会是我们想要的dp[0][length]。一根木棍有两个端点，要满足木棍由短变长，且满足左端点被最后计算，只要让第二层循环的起始参数为第一层循环参数减一即可。

for (int i = 0; i <= dots+1; i++)//dots为切割点总数
{
    for (int j =i-1; j>=0; j--){
    dp[j][i]=状态转移方程		}
}

但是两层循环还是不够，这样只能够枚举所有的子木棍，但并不能枚举子木棍的切割方式，因此还需要一层循环.

 for (int i = 0; i <= dots+1; i++)
{
    for (int j =i-1; j>=0; j--){
    for (int k = j+1; k < i; k++){
    dp[j][i] = min(dp[j][i], dp[j][k] + dp[k][i] + place[i] - place[j]);/*printf("dp[%d][%d] = %d\n", j, i, dp[j][i]);*/调试语句}}
}

代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int INFTY = 0x3f3f3f3f;
const int MAXN = 50 + 5;
int length;
int place[MAXN];
int dp[MAXN][MAXN];
int main(void)
{
    while (scanf("%d", &length) == 1 && length){
    int dots;scanf("%d", &dots);for (int i = 1; i <= dots; i++){
    scanf("%d", &place[i]);}memset(dp, INFTY, sizeof(dp));place[0] = 0;place[dots + 1] = length;for (int i = 0; i <= dots; i++){
    dp[i][i+1] = 0;}for (int i = 0; i <= dots+1; i++){
    for (int j =i-1; j>=0; j--){
    for (int k = j+1; k < i; k++){
    dp[j][i] = min(dp[j][i], dp[j][k] + dp[k][i] + place[i] - place[j]);/*printf("dp[%d][%d] = %d\n", j, i, dp[j][i]);*/}}}printf("The minimum cutting is %d.\n", dp[0][dots + 1]);}return 0;
}