http://acm.hdu.edu.cn/showproblem.php?pid=4968

给定平均分和科目数量，要求保证及格的前提下，求平均绩点的最大值和最小值。

dp[i][j]表示i个科目，总分j的情况,离线预处理以后直接输出即可

dp[i + 1][j + k] = max/min(dp[i][j] + gpa[k]);

//去掉60分以下的无用段可以提速.

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <string>

#include <queue>

#include <vector>

#include<map>

#include <iostream>

#include <algorithm>

#include <iomanip>

using namespace std;

#define RD(x) scanf("%d",&x)

#define RD2(x,y) scanf("%d%d",&x,&y)

#define clr0(x) memset(x,0,sizeof(x))

double f[12][1200];

double g[12][1200];

double gpa[120];

int main() {

    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;

    for (int i = 80; i <= 84; i++)

        gpa[i] = 3.5;

    for (int i = 85; i <= 100; i++)

        gpa[i] = 4.0;

    for (int i = 0; i <= 10; i++)

        for (int j = 0; j <= 1000; j++) {

            f[i][j] = -1e9;

            g[i][j] = 1e9;

        }

    f[0][0] = g[0][0] = 0;

    for (int i = 0; i < 10; i++) {

        for (int j = 0; j <= 1000; j++) {

            for (int k = 60; k <= 100; k++) {

                f[i + 1][j + k] = max(f[i + 1][j + k], f[i][j] + gpa[k]);

                g[i + 1][j + k] = min(g[i + 1][j + k], g[i][j] + gpa[k]);

            }

        }

    }

    int _;RD(_);

    while (_--) {

        int k, n;

        scanf("%d%d",&k,&n);

        printf("%.4lf %.4lf\n",g[n][n * k]/(double)n ,f[n][n * k ]/(double)n);

    }

    return 0;

}