[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;
}
去打赏

您的支持将鼓励我们继续创作!

[微信] 扫描二维码打赏

[支付宝] 扫描二维码打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注