`

UVA 10003 Cutting Sticks

阅读更多
//  [解题方法]
//  记忆化搜索(递归,子问题的结果用备忘录存起来,避免重复求解)
//  设棍子长度n,输入的c[i]是棍子上的坐标
//  dp[x][y](即dfs(x,y))表示砍c[x]到c[y]段的最小花费
//  每次砍c[x]~c[y]段的时候枚举砍的位置i
//  状态转移:dp[x][y] = min(dp[x][i] + dp[i][y] + c[y]-c[x])(x<=i<=y)
//  注:-1表示无穷大

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#define LL long long
#define M 55
#define inf 0x3fffffff

int dp[M][M], c[M];

int dfs (int x, int y)
{
    if (dp[x][y] > -1)
        return dp[x][y];
    int tp = -1, i;
    for (i = x+1; i < y; i++)
    {
        int tmp = dfs(x, i) + dfs(i, y) + c[y] - c[x];
        if (tp < 0 || tmp < tp) tp = tmp;
    }
    return (dp[x][y] = tp);
}

int main()
{
    int n, m, i;
    while (cin >> n, n)
    {
        cin >> m;
        c[0] = 0;
        for (i = 1; i <= m; i++) {
            cin >> c[i];
        }
        c[m+1] = n;
        memset (dp, -1, sizeof(dp));
        for (i = 0; i <= m; i++)
            dp[i][i+1] = 0;
        cout << "The minimum cutting is " << dfs(0, m+1) << "." << endl;
    }
    return 0;
}
2
1
分享到:
评论

相关推荐

    桌面便签软件Sticks

    《Sticks:一款高效便捷的桌面便签软件》 在我们的日常工作中,高效的时间管理和任务组织至关重要。桌面便签作为一种简单实用的工具,已经成为许多人的首选。今天我们要介绍的是一款名为“Sticks”的桌面便签软件,...

    sticks_backtracking

    sticks cutting problem sticks are cut randomly until all parts became less than 50 units long. Now to return sticks to the original state. This program is designed to compute the smallest possible ...

    Wood Sticks

    "Wood Sticks"似乎是一个与自然元素相关的字体主题,从标题和描述中我们可以推测这可能是一款带有木质质感或者自然风格的字体。 "Wood Sticks"字体可能是设计师为了创造一种独特的视觉效果,模拟了木质材料的质感,...

    POJ1011-Sticks

    【标题】"POJ1011 - Sticks" 是一个经典的计算机编程竞赛题目,源自北京大学的在线评测系统POJ(PKU Online Judge)。这个题目挑战程序员解决与几何图形和数学逻辑相关的问题。 【描述】该题目的核心是求解在二维...

    tech_shape_sticks

    tech_shape_sticks

    poj 2452 Sticks Problem.md

    poj 2452 Sticks Problem.md

    kdev_t.rar_sticks

    【标题】"kdev_t.rar_sticks"是一个与操作系统内核设备驱动相关的代码示例,主要涉及`kdev_t`数据类型以及如何处理设备标识符。这个压缩包包含了一些源代码文件,它们可能是用于测试、演示或实现特定功能的。 ...

    ice_sticks

    "ice_sticks"这个标题可能是指一款独特的字体设计或者一个与冰棍(ice sticks)主题相关的创意字体项目。这个项目可能旨在创造一种新颖、有趣或引人入胜的视觉效果,让人联想到冰凉、清爽的感觉,正如冰棍在炎炎夏日...

    zju1025.rar_ZJU_acm zju 10_pid_sticks_zju 1025

    【标题】"ZJU1025 Wooden Sticks" 是浙江大学(Zhejiang University,简称ZJU)在线编程竞赛平台ACM上的一道题目,编号为1025。这道题目主要考察参赛者的算法设计和实现能力,属于计算机科学中的经典问题。 【描述...

    bailian.openjudge.cn 1011 sticks

    bailian.openjudge.cn 1011 sticks

    抽象精品ppt模板tech_shape_sticks056

    抽象精品ppt模板tech_shape_sticks056

    贪心算法 WOODEN STICKS 实例代码

    Problem DescriptionThere is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs...

    POJ2513-Colored Sticks【TrieTree+MergeSet+EulerPath】

    【标题】"POJ2513-Colored Sticks【TrieTree+MergeSet+EulerPath】"涉及的是一道编程竞赛题目,主要考察参赛者的数据结构与算法应用能力,特别是Trie树(字典树)、并查集(MergeSet)以及欧拉路径(Euler Path)这...

    POJ 1011_sticks.rar

    详细解释 ,既有源代码又有书面文字解释,ppt,在VC6上完成

    WoodenSticks

    Wooden Stickes 问题 现有n 根木棒,已知它们的长度和重量。要用一部木工机一根根加工,该机器在加工过程中需要一定的准备时间,是用于清洗机器在,调整工具和模板。 木工机需要的准备时间如下: ...

    Pavilion Competition+Swiss-ster+Sticks.pdf

    【Pavilion Competition+Swiss-ster+Sticks】是一个建筑设计项目,展示了世界各国大学生的杰出建筑毕业设计作品。这个竞赛的焦点是为ETH Science City(瑞士联邦理工学院)的校园设计一个遮阳结构,旨在扩展现有的...

Global site tag (gtag.js) - Google Analytics