HDU4968-Improving the GPA

題目鏈接

題意：每個成績范圍對應一個績點，給出平均分avg，課程數n，求能得到的平均績點的最大值和最小值。

思路：先預處理出每個成績所對應的績點，然後遞推出所有情況，d[i][k]表示i個人有k分的績點總數，所以可以得到動態轉移方程。
當求最大值時d[i][k] = max(d[i][k], d[i - 1][k - j] + gpa[j])(j表示課程分數)
當求最小值時d[i][k] = min(d[i][k], d[i - 1][k - j] + gpa[j])(j表示課程分數)
注意初始化就可以了。

代碼：

#include 
#include 
#include 
#include 

using namespace std;

const int MAXN = 1005;
const int INF = 100000.0;

double dp1[15][MAXN], dp2[15][MAXN];
double gpa[MAXN];

void init() {
    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;
}

void solve() {
    memset(dp1, 0, sizeof(dp1));
    for (int i = 60; i <= 100; i++)
        dp1[1][i] = gpa[i];
    for (int i = 2; i <= 10; i++)
        for (int j = 60; j <= 100; j++)
            for (int k = j; k <= MAXN; k++)
                if (dp1[i - 1][k - j] != 0) 
                    dp1[i][k] = max(dp1[i][k], dp1[i - 1][k - j] + gpa[j]);
                

    for (int i = 0; i <= 10; i++)
        for (int j = 0; j <= MAXN; j++)
            dp2[i][j] = INF;
    for (int i = 60; i <= 100; i++)
        dp2[1][i] = gpa[i];
    for (int i = 2; i <= 10; i++)
        for (int j = 60; j <= 100; j++)
            for (int k = j; k <= MAXN; k++)
                if (dp2[i - 1][k - j] != INF) 
                    dp2[i][k] = min(dp2[i][k], dp2[i - 1][k - j] + gpa[j]); 
}

int main() {
    int cas;
    scanf("%d", &cas);
    init();
    solve();
    while (cas--) {
        int avg, n;  
        scanf("%d%d", &avg, &n);
        printf("%.4lf %.4lf\n", dp2[n][avg * n] / n, dp1[n][avg * n] / n);
    }
    return 0;
}