uva10003Cutting Sticks(DP)

题目请戳这里

题目大意:给一根木棍的长度l,再给n个数c1~cn,表示要在距木棍一端长ci处切一刀,切一刀的代价是当前所切木棍长度。求最小的总代价。

题目分析:仔细一看这其实就是一个石子合并问题,只不过换了一个姿势,一个是合并,一个是切,本质还是一样的。

我将这题转化成石子合并问题dp。

木棍切n刀会产生n+1段,他的逆过程便是将n+1堆石子合并成一堆。

dp[i][j]表示从第i段开始的j段木棍的总代价。那么i到j这一段由i到k这段+k到j这一段,所以可以枚举i到j直接的k,有方程:

dp[i][j] = min(dp[i][k] + dp[i + k][j - k] + sum(i,j),dp[i][j]);(1<= k < j);

dp[i][1] = 第i段原始长度。

注意由于每段原始长度不计入总代价,所以最后要减去原始长度,而原始长度之和正好是一个木棍长度。

详情请见代码:

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 55;
int lcm[N];
int dp[N][N];
int n,l;
int main()
{
    int i,j,k;
    while(scanf("%d",&l),l)
    {
        scanf("%d",&n);
        lcm[0] = 0;lcm[n + 1] = l;
        for(i = 1;i <= n; i ++)
            scanf("%d",lcm + i);
        sort(lcm + 1,lcm + 1 + n);
        memset(dp,1,sizeof(dp));
        for(i = 1;i <= n + 1;i ++)
            dp[i][1] = lcm[i] - lcm[i - 1];
        for(i = 2;i <= n + 1;i ++)//l
        {
            for(j = 1;i + j <= n + 2;j ++)
            {
                for(k = 1;k <= i - 1;k ++)
                    dp[j][i] = min(dp[j][i],dp[j][k] + dp[j + k][i - k] + lcm[i + j - 1] - lcm[j - 1]);
            }
        }
        printf("The minimum cutting is %d.\n",dp[1][n + 1] - l);
    }
    return 0;
}

uva10003Cutting Sticks(DP)

上一篇:微信公众号开发技术基础(一):Eclipse+Tomcat搭建本地服务器并跑通HelloWorld程序


下一篇:微信支付服务端开发