2013年9月1日

UVa 11003 - Boxes

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int SIZE = 3000 + 1;
int num[1001][SIZE], load[1001][SIZE];

int main() {
  int N;
  while (scanf("%d", &N) && N) {
    memset(num, 0, sizeof(num));
    memset(load, 0, sizeof(load));
    load[0][0] = 2e9;
    int ans = 0, limit = 0;
    for (int i = 1; i <= N; i++) {
      for (int j = 0; j <= limit; j++) {
        num[i][j] = num[i - 1][j];
        load[i][j] = load[i - 1][j];
      }
      int w, l;
      scanf("%d%d", &w, &l);
      limit = max(limit, l);
      for (int j = 0; j <= limit; j++) {
        if (load[i - 1][j] >= w) {
          int newNum = num[i - 1][j] + 1, newLoad = min(load[i - 1][j] - w, l);
          if ((num[i][newLoad] < newNum) || ((num[i][newLoad] == newNum) && (load[i][newLoad] < newLoad))) {
            num[i][newLoad] = newNum;
            load[i][newLoad] = newLoad;
            ans = max(ans, newNum);
          }
        }
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

沒有留言:

張貼留言