首页 > 代码库 > hdu 4968 Improving the GPA dp

hdu 4968 Improving the GPA dp

2024-07-18 15:33:53   227人阅读

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

 


联系
我们