hdu 4968 Improving the GPA dp

 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\n",d[sum][n]/n);
55 
56     }
57 
58     return 0;
59 }