hdu4968(分組背包)

連結：點選打開連結

題意：給出每個成績的績點，給出n科的平均成績，求n科的最大和最小平均績點

代碼：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int a,b;
double ans1,ans2;
double v[105],dp[105][1005];
int main(){
    int i,j,k,t;
    double ans1,ans2;
    for(i=60;i<=69;i++)
    v[i]=2;
    for(i=70;i<=74;i++)
    v[i]=2.5;
    for(i=75;i<=79;i++)
    v[i]=3.0;
    for(i=80;i<=84;i++)
    v[i]=3.5;
    for(i=85;i<=100;i++)
    v[i]=4;
    scanf("%d",&t);
    while(t--){                                 //因為有n科，相當于分組背包，每次至少拿一個
        scanf("%d%d",&a,&b);
        a*=b;
        for(i=0;i<=b;i++)
        for(j=0;j<=a;j++)
        dp[i][j]=-1;
        dp[0][0]=0;                             //最大值
        for(i=1;i<=b;i++){
        for(j=a;j>=0;j--){
        for(k=60;k<=100;k++){
            if(k>j)
            break;
            if(dp[i-1][j-k]!=-1)
            dp[i][j]=max(dp[i][j],dp[i-1][j-k]+v[k]);
        }
        }
        }
        ans1=dp[b][a];
        for(i=0;i<=b;i++)
        for(j=0;j<=a;j++)
        dp[i][j]=10000;
        dp[0][0]=0;                             //最小值
        for(i=1;i<=b;i++)
        for(j=a;j>=0;j--){
        for(k=60;k<=100;k++){
            if(k>j)
            break;
            if(dp[i-1][j-k]!=10000)
            dp[i][j]=min(dp[i][j],dp[i-1][j-k]+v[k]);
        }
        }
        ans2=dp[b][a];
        printf("%.4lf %.4lf\n",ans2/b,ans1/b);
    }
    return 0;
}