给你一根长为 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;
}

打赏 赞(0)

微信

支付宝

用微信扫描二维码打赏

用支付宝扫描二维码打赏