首页 > 代码库 > hdu 4968 Improving the GPA dp
hdu 4968 Improving the GPA dp
【题意】:每个成绩范围对应一个绩点,给出平均分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 999999910 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\n",d[sum][n]/n);55 56 }57 58 return 0;59 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。