// [解题方法]
// 记忆化搜索(递归,子问题的结果用备忘录存起来,避免重复求解)
// 设棍子长度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;
}
分享到:
相关推荐
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
国外的一款免安装版的桌面便签软件,支持定时提醒,方便大家管理纷繁复杂的工作事物
北大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
北大POJ2513-Colored Sticks【TrieTree+MergeSet+EulerPath】 解题报告+AC代码
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...
zju 1025 Wooden Sticks http://acm.zju.edu.cn/show_problem.php?pid=1025
详细解释 ,既有源代码又有书面文字解释,ppt,在VC6上完成
Wooden Stickes 问题 现有n 根木棒,已知它们的长度和重量。要用一部木工机一根根加工,该机器在加工过程中需要一定的准备时间,是用于清洗机器在,调整工具和模板。 木工机需要的准备时间如下: ...