2013年8月31日

UVa 11856 - Ferry Loading V

Don't assume all of the real number in this problem are bigger than 0.01.
WA + TLE 20times, almost 3 hours...
#include <cstdio>

const int SIZE = 10000;
int index[SIZE], prev[SIZE];

void show(int sum, bool first) {
  if (!sum) {
    return;
  }
  show(prev[sum], false);
  printf("%d%s", index[sum], first ? "\n" : " ");
}

int main() {
  int n;
  while (scanf("%d", &n) && n) {
    double sum = 0, temp[101];
    for (int i = 1; i <= n; i++) {
      scanf("%lf", &temp[i]);
      sum += temp[i];
    }
    int w[101];
    for (int i = 0; i <= n; i++) {
      w[i] = temp[i] * SIZE / sum;
      prev[i] = 0;
    }
    int limit = SIZE / 2, last = 0;
    bool dp[SIZE / 2] = {true};
    for (int i = 1; i <= n; i++) {
      for (int j = limit; j >= w[i]; j--) {
        if (!dp[j] && dp[j - w[i]]) {
          dp[j] = true;
          prev[j] = j - w[i];
          index[j] = i;
          last = j > last ? j : last;
        }
      }
    }
    show(last, true);
  }
  return 0;
}

沒有留言:

張貼留言