uva 10003 Cutting Sticks 【区间dp】

青旅半醒 2022-08-12 03:58 29阅读 0赞

题目：[uva 10003 Cutting Sticks][]

题意：给出一根长度 l 的木棍，要截断从某些点，然后截断的花费是当前木棍的长度，求总的最小花费？

分析：典型的区间dp，其实和石子归并是一样的，花费就是石子的和，那么久不用多说了。

AC代码：

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include <map>
    #include <cmath>
    #include <vector>
    #include <algorithm>
    using namespace std;
    const int inf = 0x3f3f3f3f;
    const int N = 65;
    int a[N];
    int dp[N][N];
    int main()
    {
        int chang,n,x;
        while(~scanf("%d",&chang) && chang)
        {
            memset(dp,0x3f3f3f3f,sizeof(dp));
            scanf("%d",&n);
            a[0]=0,a[n+1]=chang;
            for(int i=1;i<=n;i++){
                scanf("%d",&a[i]);
            }
            n+=2;
            for(int i=0;i<=n;i++)
                dp[i][i+1]=0;
            for(int len=2;len<=n;len++)
            {
                for(int l=0;(l+len)<n;l++)
                {
                    int r=l+len;
                    for(int i=l+1;i<r;i++)
                        dp[l][r]=min(dp[l][r],dp[l][i]+dp[i][r]+(a[r]-a[l]));
                    //printf("xx%d %d %d\n",l,r,dp[l][r]);
                }
            }
            printf("The minimum cutting is %d.\n",dp[0][n-1]);
        }
        return 0;
    }

[uva 10003 Cutting Sticks]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=944

发表评论取消回复

表情：

评论列表（有 0 条评论，29人围观）

还没有评论，来说两句吧...

相关阅读

相关 UVA 10529 - Dumb Bones（概率+区间dp)

UVA 10529 - Dumb Bones [题目链接][Link 1] [Link 1]: http://uva.onlinejudge.org/index.ph

桃扇骨/ 2024年02月17日 21:57/ 0 赞/ 69 阅读

相关 UVA 1626 括号序列（区间dp）

分析：区间dp，装填方程：dp(i,j)=min(dp(i,k)+dp(k+1,j)) 其中（i<=k<j） dp(i,j)表示从第i个字符到第j个字符的最小需要添加括号字符的

Myth丶恋晨/ 2024年02月17日 19:36/ 0 赞/ 72 阅读

相关 UVA 10003 切木棍（区间dp）

思路：本题是一个区间dp题，状态方程dp(i,j)=max(dp(i,k)+dp(k,j)+v\[j\]-v\[i\]) 其中(i<k<j) ，dp表示从i到j的最小花费。

客官°小女子只卖身不卖艺/ 2024年02月17日 19:36/ 0 赞/ 51 阅读

相关 uva 10003——Cutting Sticks

题意：给定一长为L的木棍和n个切割点，每次切割的费用为切割的长度，求最小的费用。思路：dp,子问题是区间（i，j）的最小费用，临界是（i,j)只有一个切割点。dp

曾经终败给现在/ 2022年08月17日 14:24/ 0 赞/ 22 阅读

相关 uva 10003 Cutting Sticks 【区间dp】

题目：[uva 10003 Cutting Sticks][] 题意：给出一根长度 l 的木棍，要截断从某些点，然后截断的花费是当前木棍的长度，求总的最小花费？

青旅半醒/ 2022年08月12日 03:58/ 0 赞/ 30 阅读

相关 uva 10003 动态规划

给定一个长度为len的木板，要在n个位置处切开，每次切开的代价是这块木板的长度，求最小的代价。其实切木板跟合并木板是等价的。。开始以为是简单的贪心，便写了一个优先

待我称王封你为后i/ 2022年08月03日 13:41/ 0 赞/ 37 阅读

相关 UVA 10003 区间DP

题意：有一根长度为l的木棍，木棍上面有m个切割点，每一次切割都要付出当前木棍长度的代价，问怎样切割有最小代价。分析：石子合并的逆过程。状态：设F（i，j）为区间(

绝地灬酷狼/ 2021年12月18日 15:19/ 0 赞/ 272 阅读

相关 UVA1336 - Fixing the Great Wall （区间DP）

题意：用机器人修复分布在一条直线段上的n个损坏点，对于每个点i，x\[i\]表示位置，c\[i\]为立刻修缮的费用，d\[i\]为单位时间增加的维修费用。例如若在时刻t修缮i

小鱼儿/ 2021年12月14日 22:31/ 0 赞/ 224 阅读

相关 uva10559 Blocks（区间DP 增加维度）

题意：每次可以选择一个区间（连续相同的序列）消除，得分为 len\len；问最大得分。分析：紫书P298-299，很详细。 LRJ代码：

叁歲伎倆/ 2021年12月13日 17:27/ 0 赞/ 252 阅读

相关 UVA 10003 Cutting Sticks 区间DP

题目大意：给你一个长度为L的木条，和N个切割点，每次切割的代价是当前切割木条的长度，问最小代价是多少。　　解题思路：很显然的区间DP， dp(i, j)表示...

红太狼/ 2021年03月30日 15:53/ 0 赞/ 435 阅读