【题意】：每个成绩范围对应一个绩点，给出平均分avg，课程数n，求能得到的平均绩点的最大值和最小值。
【解法】： d[i][j]表示总分为i 课程数为j时 可以得到的最大的总绩点。
状态转移为： d[i][j]=max(d[i][j],d[i-k][j-1]+d[k][1]); (60<=k<=100&&i-k>=60*(j-1))
1 #include<iostream> 2 #include<cstdio> 3 #include<map> 4 #include<algorithm> 5 #include<cstring> 6 using namespace std; 7 double temp[102]; 8 double d[1002][12]; 9 #define INF 9999999 10 11 int main() 12 { 13 14 int n,m,sum,t; 15 for(int i=60;i<=69;i++) 16 temp[i]=2.0; 17 for(int i=70;i<=74;i++) 18 temp[i]=2.5; 19 for(int i=75;i<=79;i++) 20 temp[i]=3.0; 21 for(int i=80;i<=84;i++) 22 temp[i]=3.5; 23 for(int i=85;i<=100;i++) 24 temp[i]=4.0; 25 26 scanf("%d",&t); 27 while(t--) 28 { 29 scanf("%d%d",&m,&n); 30 sum=m*n; 31 for(int i=0;i<=sum;i++) 32 for(int j=0;j<=n;j++) 33 d[i][j]=INF; 34 for(int i=60;i<=100;i++) 35 d[i][1]=temp[i]; 36 37 for(int j=2;j<=n;j++) 38 for(int i=0;i<=sum;i++) 39 for(int k=60;k<=100&&(i-k>=60*(j-1));k++) 40 d[i][j]=min(d[i][j],d[i-k][j-1]+d[k][1]); 41 printf("%.4lf ",d[sum][n]/n); 42 43 for(int i=0;i<=sum;i++) 44 for(int j=0;j<=n;j++) 45 d[i][j]=0; 46 47 for(int i=60;i<=100;i++) 48 d[i][1]=temp[i]; 49 50 for(int j=2;j<=n;j++) 51 for(int i=0;i<=sum;i++) 52 for(int k=60;k<=100&&(i-k>=60*(j-1));k++) 53 d[i][j]=max(d[i][j],d[i-k][j-1]+d[k][1]); 54 printf("%.4lf ",d[sum][n]/n); 55 56 } 57 58 return 0; 59 }