题目链接

题意：每个成绩范围对应一个绩点，给出平均分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; }