2014年1月31日

UVa 10086 - Test the Rods

#include <cstdio>
 
int main() {
  int T1 ,T2;
  while (scanf("%d%d", &T1, &T2) && (T1 + T2)) {
    int n;
    scanf("%d", &n);
    int num[31], cost[2][31][21];
    for (int i = 1; i <= n; i++) {
      scanf("%d", num + i);
      cost[0][i][0] = cost[1][i][0] = 0;
      for (int j = 1; j <= num[i]; j++) {
        scanf("%d", &cost[0][i][j]);
      }
      for (int j = 1; j <= num[i]; j++) {
        scanf("%d", &cost[1][i][j]);
      }
    }
    int sum = 0, dp[31][301], pick[31][301];
    for (int i = 0; i <= n; i++) {
      for (int t1 = 0; t1 <= T1; t1++) {
        dp[i][t1] = 1e8;
      }
    }
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
      sum += num[i];
      for (int use = num[i]; use >= 0; use--) {
        for (int t1 = sum < T1 ? sum : T1; t1 >= use; t1--) {
          int value = dp[i - 1][t1 - use] + cost[0][i][use] + cost[1][i][num[i] - use];
          if (value < dp[i][t1]) {
            dp[i][t1] = value;
            pick[i][t1] = use;
          }
        }
      }
    }
    printf("%d\n", dp[n][T1]);
    int i = n, t1 = T1, ans[31];
    while (i) {
      ans[i] = pick[i][t1];
      t1 -= ans[i];
      i--;
    }
    for (int i = 1; i <= n; i++) {
      printf("%d%s", ans[i], i == n ? "\n\n" : " ");
    }
  }
  return 0;
}

沒有留言:

張貼留言