2013年5月20日

UVa 10003 - Cutting Sticks


#include <stdio.h>

int main() {
  int len;
  while (scanf("%d", &len) && len) {
    int n, pos[99], dp[99][99];
    scanf("%d", &n);
    int i, j, k, l;
    for (i = 1; i <= n; i++)
      scanf("%d", &pos[i]);
    pos[0] = 0;
    pos[n + 1] = len;
    for (k = 2; k <= n + 1; k++)
      for (i = 0; i <= n - k + 1; i++) {
        j = i + k;
        dp[i][j] = 1e9;
        for (l = i + 1; l < j; l++) {
          int cost = dp[i][l] + dp[l][j] + pos[j] - pos[i];
          dp[i][j] = dp[i][j] < cost ? dp[i][j] : cost;
        }
      }
    printf("The minimum cutting is %d.\n", dp[0][n + 1]);
  }
  return 0;
}

沒有留言:

張貼留言