P*******b
发帖数: 1001 | 1 Given a line segment of length n. You need to cut it into m pieces specified
by position[n] array. The price of cutting a segment of length len in two p
arts is always len (irrespective of cut position). Give a dynamic programmin
g solution to minimize the cost of cutting |
h**6
发帖数: 4160 | 2 直观分析，每次都对半砍。用DP解的话，应该是个 O(m^3) 的问题。
You need to cut it into m pieces specified by position[n] array.
这句话可能不太对，我理解为数组 position[m+1] 表示切割位置，其中 position[0]=0，position[m]=n，而 position[1...m-1] 表示 m-1 处切割。
设 dp[i][j] 为把切割点 i,j 之间的线段完全切割的代价，那么 dp[0][m] 为所求答案。
初始条件：
dp[i][i+1] = 0
设 k 为第一刀的位置，则 i
dp[i][j] = min(k=i+1 to j-1)(dp[i][k]+dp[k][j]+position[j]-position[i]) |
t****a
发帖数: 1212 | 3 han6 come first
qu you wu, zhou lang gu :)
here goes DP solution, as han6 said, O(m^3)
#ifdef HAVE_CONFIG_H
#include
#endif
#include
#include
int cost[100][100];
int best_cut(int position[], int start, int stop) {
// printf("%d\t%d\n", start, stop);
if (cost[start][stop]!=-1) {
return(cost[start][stop]);
} else {
int cost0 = position[stop] - position[start];
if (start+1 == stop) {
cost[start][stop] = cost0;
|
v********w
发帖数: 136 | 4 奇怪,为什么你的回帖后半段恢复时才能看到,agree 你的dp解，但直观对半砍好像不对
]=0，position[m]=n，而 position[1...m-1] 表示 m-1 处切割。
答案。
【在 h**6 的大作中提到】
: 直观分析，每次都对半砍。用DP解的话，应该是个 O(m^3) 的问题。
: You need to cut it into m pieces specified by position[n] array.
: 这句话可能不太对，我理解为数组 position[m+1] 表示切割位置，其中 position[0]=0，position[m]=n，而 position[1...m-1] 表示 m-1 处切割。
: 设 dp[i][j] 为把切割点 i,j 之间的线段完全切割的代价，那么 dp[0][m] 为所求答案。
: 初始条件：
: dp[i][i+1] = 0
: 设 k 为第一刀的位置，则 i: dp[i][j] = min(k=i+1 to j-1)(dp[i][k]+dp[k][j]+position[j]-position[i])
|
y***d
发帖数: 2330 | 5 cutting points 是预先给定的还是咋地？
specified
p
programmin
【在 P*******b 的大作中提到】
: Given a line segment of length n. You need to cut it into m pieces specified
: by position[n] array. The price of cutting a segment of length len in two p
: arts is always len (irrespective of cut position). Give a dynamic programmin
: g solution to minimize the cost of cutting
|
K******g
发帖数: 1870 | 6 我觉得你简化了这道题。
这道题还有一层意思，从n个position中挑出m个position出来，找出所有组合的最小代
价。你直接把position定义为m个了。
]=0，position[m]=n，而 position[1...m-1] 表示 m-1 处切割。
答案。
【在 h**6 的大作中提到】
: 直观分析，每次都对半砍。用DP解的话，应该是个 O(m^3) 的问题。
: You need to cut it into m pieces specified by position[n] array.
: 这句话可能不太对，我理解为数组 position[m+1] 表示切割位置，其中 position[0]=0，position[m]=n，而 position[1...m-1] 表示 m-1 处切割。
: 设 dp[i][j] 为把切割点 i,j 之间的线段完全切割的代价，那么 dp[0][m] 为所求答案。
: 初始条件：
: dp[i][i+1] = 0
: 设 k 为第一刀的位置，则 i: dp[i][j] = min(k=i+1 to j-1)(dp[i][k]+dp[k][j]+position[j]-position[i])
|
h**6
发帖数: 4160 | 7 这题和前两天我发的取珠宝的问题几乎是一个模子出来的，不过我更习惯于纯 DP 的解
法，而不是类似于填空的假递归。
int best_cut(const vector position)
{
int m = position.size()-1;
vector > dp(m+1, vector(m+1));
for(int i=0; i
dp[i][i+1] = 0;
for(int len=2; len<=m; len++)
{
for(int begin=0; begin<=m-len; begin++)
{
int end = begin+len;
int cost = INT_MAX;
for(int k=begin+1; k<=end-1; k++)
cost = min(cost, dp[begin][k]+dp[k][end]) |
h**6
发帖数: 4160 | 8 楼主的 n 既表示长度，又表示可切割的点，所以不是很明白到底是什么含义。
如果按照这个理解，可以再定义一维，dp[i][j][x]表示i到j的线段切成x段的代价，一
样能做出来。
【在 K******g 的大作中提到】
: 我觉得你简化了这道题。
: 这道题还有一层意思，从n个position中挑出m个position出来，找出所有组合的最小代
: 价。你直接把position定义为m个了。
:
: ]=0，position[m]=n，而 position[1...m-1] 表示 m-1 处切割。
: 答案。
|
K******g
发帖数: 1870 | 9 这个就复杂了，应为i到j之间的割法有很多种，存在一个组合问题。这道题目要code出
来，需要点时间啊
【在 h**6 的大作中提到】
: 楼主的 n 既表示长度，又表示可切割的点，所以不是很明白到底是什么含义。
: 如果按照这个理解，可以再定义一维，dp[i][j][x]表示i到j的线段切成x段的代价，一
: 样能做出来。
|
h**k
发帖数: 3368 | 10 多加一层循环就够了
【在 K******g 的大作中提到】
: 这个就复杂了，应为i到j之间的割法有很多种，存在一个组合问题。这道题目要code出
: 来，需要点时间啊
|
