HDU 4968 Improving the GPA 解題：完整 DP 表法求極值 GPA

題目重述

同 ID 208658，此處給出另一種 DP 實作：直接對分數 60-100 建立映射表，雙層 DP 填表。

分數到 GPA 映射

double gpa[101];
for (int i=60;i<=69;++i) gpa[i]=2.0;
for (int i=70;i<=74;++i) gpa[i]=2.5;
for (int i=75;i<=79;++i) gpa[i]=3.0;
for (int i=80;i<=84;++i) gpa[i]=3.5;
for (int i=85;i<=100;++i) gpa[i]=4.0;

DP 定義

• dp_max[i][s]：前 i 門課，總分為 s 的最大 GPA 總和。
• dp_min[i][s]：最小 GPA 總和 (初始化為 INF)。

轉移

for (int i=1;i<=10;++i)
    for (int score=60;score<=100;++score)
        for (int s=score;s<=1000;++s)
            if (dp_max[i-1][s-score] > 0) // 可達
                dp_max[i][s] = max(dp_max[i][s], dp_max[i-1][s-score] + gpa[score]);
            if (dp_min[i-1][s-score] < INF)
                dp_min[i][s] = min(dp_min[i][s], dp_min[i-1][s-score] + gpa[score]);

查詢

總分 S = avg * N。輸出 dp_min[N][S]/N 和 dp_max[N][S]/N (保留 4 位小數)。

優缺點

此法狀態上限 1000 (10*100)，略大於扣除 60 後的 400，但邏輯直觀，無需偏移轉換。