题意:把一根木棍按给定的n个点切下去,每次切的花费为切的那段木棍的长度,求最小花费。
这题出在dp入门这边,但是我看完题后有强烈的既是感,这不是以前做过的石子合并的题目变形吗?
题目其实就是把n+1根木棍合并成一只长木棍,花费为合并后的木棍长度。
于是我很开心地用优先队列敲完代码,wa了。。。
后来发现两个木棍的序号必须是连续的,用优先队列会把序号打乱。每次删减中间的一个数又很费时间,于是想到用list+递归,就当我得意的敲出代码,过了不少代码时,它继续给我wa了。。。
我非常郁闷的在board上找样例,发现有几组是过不了的,比如:
111
10
10 17 28 30 37 44 47 49 77 94
然后我就跪了,单步去调试,发现贪心没写错。
于是跟基友讨论未果,然后在网上找到了这个:石子合并问题
看来贪心时可能会对接下去的计算产生影响,所以不一定是最优解。。。
下面才是正解 TAT:
这题只能用dp做法了。。。用d[begin][end]表示从bigin切点到end切点,这段木棍的最省钱切法,然后就模拟切中间各点,计算交给递归下一层。。。
没有后效性,记忆化搜索,子问题重叠,这三个是dp题目的基本要素。
这题让我学到很多东西,我体验了贪心并不是最优解这一惨痛事实,让我更加体会到dp的思想。
代码:
/*
* Author: illuz <iilluzen[at]gmail.com>
* Blog: http://blog.csdn.net/hcbbt
* File: _uva10003.cpp
* Create Date: 2013-09-20 16:04:57
* Descripton: dp
*/
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 55;
int s[MAXN], d[MAXN][MAXN], len, n;
int dp(int b, int e) {
if (d[b][e] >= 0) return d[b][e];
d[b][e] = dp(b, b + 1) + dp(b + 1, e) + s[e] - s[b];
for (int i = b + 2; i < e; i++) {
int tt = dp(b, i) + dp(i, e) + s[e] - s[b];
d[b][e] = min(d[b][e], tt);
}
return d[b][e];
}
int main() {
while (scanf("%d", &len) && len) {
scanf("%d", &n);
for (int i = 0; i <= n + 1; i++)
for (int j = 0; j <= n + 1; j++)
if (j - i == 1)
d[i][j] = 0;
else
d[i][j] = -1;
for (int i = 0; i < n; i++)
scanf("%d", &s[i + 1]);
s[n + 1] = len;
printf("The minimum cutting is %d.\n", dp(0, n + 1));
}
return 0;
}
分享到:
相关推荐
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
国外的一款免安装版的桌面便签软件,支持定时提醒,方便大家管理纷繁复杂的工作事物
Wooden Stickes 问题 现有n 根木棒,已知它们的长度和重量。要用一部木工机一根根加工,该机器在加工过程中需要一定的准备时间,是用于清洗机器在,调整工具和模板。 木工机需要的准备时间如下: ...
北大POJ1011-Sticks 解题报告+AC代码
tech_shape_sticks
poj 2452 Sticks Problem.md
Very simple example code - sticks a sortkey in the buffer Not much error checking.
ice_sticks
bailian.openjudge.cn 1011 sticks
抽象精品ppt模板tech_shape_sticks056
切棒问题陈述给您N条棍棒,其中每根棍棒的长度为正整数。 对木棍进行切割操作,以使所有木棍都减小最小木棍的长度。 假设我们有以下长度的六根木棍: 5 4 4 2 2 8然后,在一次切割操作中,我们从六根木棍中的每根...
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】 解题报告+AC代码
zju 1025 Wooden Sticks http://acm.zju.edu.cn/show_problem.php?pid=1025
详细解释 ,既有源代码又有书面文字解释,ppt,在VC6上完成