2014年2月1日

UVa 11341 - Term Strategy

#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int N, M;
    scanf("%d%d", &N, &M);
    int dp[11][101] = {}, sum = 0;
    for (int i = 1; i <= N; i++) {
      for (int j = 1; j <= M; j++) {
        int grade;
        scanf("%d", &grade);
        for (int w = M; grade >= 5 && w >= j; w--) {
          if ((i == 1 && w == j) || dp[i - 1][w - j]) {
            dp[i][w] = max(dp[i][w], dp[i - 1][w - j] + grade);
            if (i == N && dp[i][w] > sum) {
              sum = dp[i][w];
            }
          }
        }
      }
    }
    if (sum) {
      printf("Maximal possible average mark - %.2lf.\n", sum / (double)N + 1e-9);
    } else {
      puts("Peter, you shouldn't have played billiard that much.");
    }
  }
  return 0;
}

沒有留言:

張貼留言