2013年8月31日

UVa 12563 - Jin Ge Jin Qu hao

#include <cstdio>
#include <map>
using namespace std;

int main() {
  int T, C = 1;
  scanf("%d", &T);
  while (T--) {
    int n, t;
    scanf("%d%d", &n, &t);
    map<int, int> dp;
    dp[0] = 0;
    int maxTime = 0, maxLen = 0;
    for (int i = 0; i < n; i++) {
      int l;
      scanf("%d", &l);
      map<int, int> next = dp;
      for (map<int, int>::iterator it = dp.begin(); it != dp.end(); it++) {
        int len = it->first, times = it->second;
        if (l + len < t) {
          next[l + len] = max(next[l + len], times + 1);
          if ((times + 1) > maxTime || ((times + 1) == maxTime && (l + len) > maxLen)) {
            maxTime = times + 1;
            maxLen = l + len;
          }
        }
      }
      dp = next;
    }
    printf("Case %d: %d %d\n", C++, maxTime + 1, maxLen + 678);
  }
  return 0;
}

沒有留言:

張貼留言