d196. 11341 - Term Strategy
http://zerojudge.tw/ShowProblem?problemid=d196
內容 ：
學生彼得整學期都在玩撞球因而錯過了所有的課堂。不幸的是現在彼得必須通過他的期末考。
彼得修了N (1 <= N <= 10) 門課。時間已無多而且他答應老師要一天之內考完所有的試。他的哲學是「全拿或全輸」。在他做了一天只玩 5 小時撞球的假設及一些考量之後，他算出了他還有 M (0 < M <= 100) 個小時可以準備考試。在準備一個科目時，他至少得讀完該科目的名稱，由於這個困難的工作，每科至少要準備一個小時。如果有任何一科沒有準備，該科就會當掉。
考試的成績分為 10 級分。彼得要得到 5 級分才能及格。彼得也是個貪心的人，他希望平均成績越高越好。
由於彼得完全清楚自己的實力，他做了一個表格 L。表格中的每一列代表一科，每一欄代表彼得在該科所花的時間。Lij 代表彼得如果用 j 個小時去準備第 i 科時所能得到的成績。已知彼得在某科目所用的時間越多，所得的成績也會越高，也就是說. Li j >= Li j+1 。
彼得突然想到他有一個好友。事實上，他所想到的人就是你。由於情況緊急，他請你幫忙找出可以 All Pass 並得到最高平均成績的方法。
輸入說明
：
輸入的第一行會給你測試資料的組數T (T < 100)。每組測資的第一行有兩個整數N 和 M。接下來的 N 行每行有 M 個整數代表 Li j。
輸出說明
：
對於每組測資，請找出彼得是否可以 All Pass。如果他可以 All Pass 請印出一行：「Maximal possible average mark - S. 」(答案 S 必須四拾五入到小數點以下兩位)。
如果他不幸會當掉至少一科的話，則印出一行：「Peter, you shouldn't have played billiard that much.」(彼得，你不該打那麼多撞球的。)
範例輸入 ：
2 4 5 5 5 6 7 8 5 5 6 7 8 5 6 7 8 8 6 7 8 9 9 4 5 4 5 6 7 8 4 5 6 7 8 5 6 7 8 8 6 7 8 9 9
範例輸出 ：
Maximal possible average mark - 5.50. Peter, you shouldn't have played billiard that much.
提示
：
若得到 WA (line:10) 請留意浮點數誤差。
出處
：
作法 : DP
網路上貌似有ppt的說明，不過好像是寫錯了
min應該取max去做
A[a,b] 總共讀了 1~a 科，共花了 b 分鐘，可以得到的最高分數
遞迴部份，如程式所附 ...
/**********************************************************************************/
/* Problem: d196 "11341 - Term Strategy" from UVa ACM 11341 */
/* Language: C */
/* Result: AC (4ms, 310KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-15 17:54:02 */
/**********************************************************************************/
#include<stdio.h>
main() {
int T, n, m;
scanf("%d", &T);
while(T--) {
scanf("%d %d", &n, &m);
int L[11][101] = {}, a, b, c;
for(a = 1; a <= n; a++)
for(b = 1; b <= m; b++)
scanf("%d", &L[a][b]);
int A[11][101] = {};/*A[a,b] 總共讀了 1~a 科，共花了 b 分鐘*/
for(a = 1; a <= m; a++)
if(L[1][a] >=5)
A[1][a] = L[1][a];
for(a = 2; a <= n; a++) {
for(b = 1; b <= m; b++) {
int max = 0;
for(c = 1; c <= b; c++) /*花多久時間*/
if(L[a][c] >= 5 && A[a-1][b-c]) {
if(max < L[a][c] + A[a-1][b-c]) {
max = L[a][c] + A[a-1][b-c];
}
}
A[a][b] = max;
}
}
if(A[n][m] == 0)
puts("Peter, you shouldn't have played billiard that much.");
else
printf("Maximal possible average mark - %.2lf.\n", (double)A[n][m]/n + 1e-9);
}
return 0;
}