[UVA10003] Cutting Sticks
2017年8月27日给你一根长为 l 的线段,让你在这线段上的 n 个位置进行切割,切割的费用为线段的长度。比如长度为10的线段,在7这个位置进行切割,费用为10,切割后产生两个线段,让你求切完 n 个位置的最小花费。
想法是把线段分成 n + 1 个区间。这样以来,当区间长度为 1 时,就相当于不用切割的状态,这时费用为0;当区间长度为 2 时,费用为这个区间对应线段的长度;当区间长度为 3 或以上时,将其分成两部分,这两部分所需费用加上区间对应线段的长度就是总费用。
这样递推一下就好了。
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int a[N];
int dp[N][N];
int main()
{
int l;
while (~scanf("%d", &l) && l) {
int n;
scanf("%d", &n);
memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
}
a[0] = 0;
a[n + 1] = l;
for (int i = 1; i <= n + 1; i++) {
for (int j = 0; j + i <= n + 1; j++) {
if (i == 1) {
dp[j][j + i] = 0;
}
for (int k = j + 1; k < i + j; k++) {
dp[j][j + i] = min(dp[j][j + i], dp[j][k] + dp[k][j + i] + a[i + j] - a[j]);
}
}
}
printf("The minimum cutting is %d.\n", dp[0][n + 1]);
}
return 0;
}