2013年8月26日

UVa 990 - Diving for Gold

#include <cstdio>
#include <cstring>

struct Treasure {
  int d, v;
} trea[99];


int t, w, dp[33][1111], use[33][1111];

void show(int i, int time, int num) {
  if (!i) {
    printf("%d\n", num);
    return;
  }
  if (use[i][time]) {
    Treasure & treasure = trea[use[i][time]];
    show(i - 1, time - treasure.d * w * 3, num + 1);
    printf("%d %d\n", treasure.d, treasure.v);
  } else {
    show(i - 1, time, num);
  }
}


int main() {
  bool first = true;
  while (scanf("%d%d", &t, &w) == 2) {
    if (!first) {
      puts("");
    }
    first = false;
    memset(dp, 0, sizeof(dp));
    memset(use, 0, sizeof(use));
    int n, cost = 0, ans = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
      for (int j = 0; j <= t; j++) {
        dp[i][j] = dp[i - 1][j];
      }
      scanf("%d%d", &trea[i].d, &trea[i].v);
      int need = trea[i].d * w * 3;
      for (int j = need; j <= t; j++) {
        if (dp[i][j] < dp[i - 1][j - need] + trea[i].v) {
          dp[i][j] = dp[i - 1][j - need] + trea[i].v;
          use[i][j] = i;
          if (dp[i][j] > ans) {
            ans = dp[i][j];
            cost = j;
          }
        }
      }
    }
    printf("%d\n", ans);
    show(n, cost, 0);
  }
  return 0;
}

沒有留言:

張貼留言