POJ 4968 DP||记忆化搜索

给出N个人的平局分X

根据GPA规则计算可能的最高平均GPA和最低平均GPA

可以DP预处理出来所有结果  或者记忆化搜索

DP：

#include "stdio.h"
#include "string.h"
int inf=100000000;

double a[11][1100],b[11][1100];

double Max(double a,double b)
{
    if (a<b) return b; else return a;
}

double Min(double a,double b)
{
    if (a<b) return a;else return b;
}
int main()
{
    int Case,i,j,x,k;
    for (i=0;i<=1000;i++)
        for (j=0;j<=10;j++)
        {
            a[j][i]=inf;
            b[j][i]=-1;
        }

    a[0][0]=b[0][0]=0;

    for (i=1;i<=10;i++)
        for (j=60*i;j<=100*i;j++)
        {
            for (k=60;k<=69;k++)
                if (j-k>=0 && a[i-1][j-k]!=inf)
                    a[i][j]=Min(a[i][j],a[i-1][j-k]+2);

            for (k=70;k<=74;k++)
                if (j-k>=0 && a[i-1][j-k]!=inf)
                    a[i][j]=Min(a[i][j],a[i-1][j-k]+2.5);

            for (k=75;k<=79;k++)
                if (j-k>=0 && a[i-1][j-k]!=inf)
                    a[i][j]=Min(a[i][j],a[i-1][j-k]+3);

            for (k=80;k<=84;k++)
                if (j-k>=0 && a[i-1][j-k]!=inf)
                    a[i][j]=Min(a[i][j],a[i-1][j-k]+3.5);

            for (k=85;k<=100;k++)
                if (j-k>=0 && a[i-1][j-k]!=inf)
                    a[i][j]=Min(a[i][j],a[i-1][j-k]+4);
        }

    for (i=1;i<=10;i++)
        for (j=60*i;j<=100*i;j++)
        {
            for (k=60;k<=69;k++)
                if (j-k>=0 && b[i-1][j-k]!=-1)
                    b[i][j]=Max(b[i][j],b[i-1][j-k]+2);

            for (k=70;k<=74;k++)
                if (j-k>=0 && b[i-1][j-k]!=-1)
                    b[i][j]=Max(b[i][j],b[i-1][j-k]+2.5);

            for (k=75;k<=79;k++)
                if (j-k>=0 && b[i-1][j-k]!=-1)
                    b[i][j]=Max(b[i][j],b[i-1][j-k]+3);

            for (k=80;k<=84;k++)
                if (j-k>=0 && b[i-1][j-k]!=-1)
                    b[i][j]=Max(b[i][j],b[i-1][j-k]+3.5);

            for (k=85;k<=100;k++)
                if (j-k>=0 && b[i-1][j-k]!=-1)
                    b[i][j]=Max(b[i][j],b[i-1][j-k]+4);
        }

    scanf("%d",&Case);
    while (Case--)
    {
        scanf("%d%d",&x,&i);
        printf("%.4lf %.4lf\n",a[i][i*x]/i,b[i][i*x]/i);
    }
    return 0;
}

#include "stdio.h"
#include "string.h"

int dira[]={100,84,79,74,69};
int dirb[]={85,80,75,70,60};
double mark[]={4,3.5,3,2.5,2};

double a[1010][11],b[1010][11];

double MMin(double a,double b)
{
    if (a<b) return a; else return b;
}

double MMax(double a,double b)
{
    if (a<b) return b; else return a;
}

double dfs_min(int sum,int n)
{
    double ans,temp;
    int i;
    if (a[sum][n]!=-1) return a[sum][n];

    ans=500000;
    for (i=0;i<5;i++)
    {
        temp=sum-dira[i];
        if (n!=1 && (temp/(n-1)<60 || temp/(n-1)>100)) continue;
        ans=MMin(ans,dfs_min(temp,n-1)+mark[i]);
    }
    return a[sum][n]=ans;
}

double dfs_max(int  sum,int n)
{
    double ans,temp;
    int i;
    if (b[sum][n]!=-1) return b[sum][n];

    ans=0;
    for (i=0;i<5;i++)
    {
        temp=sum-dirb[i];
        if (n!=1 && (temp/(n-1)<60 || temp/(n-1)>100)) continue;
        ans=MMax(ans,dfs_max(temp,n-1)+mark[i]);
    }
    return b[sum][n]=ans;
}
int main()
{
    int Case,i,n,j,x;
    double Max,Min;
    scanf("%d",&Case);
    while (Case--)
    {
        scanf("%d%d",&x,&n);

        for (i=0;i<=1000;i++)
            for (j=0;j<=10;j++)
            a[i][j]=b[i][j]=-1;
        for (i=60;i<=69;i++)
            a[i][1]=b[i][1]=2;
        for (i=70;i<=74;i++)
            a[i][1]=b[i][1]=2.5;
        for (i=75;i<=79;i++)
            a[i][1]=b[i][1]=3;
        for (i=80;i<=84;i++)
            a[i][1]=b[i][1]=3.5;
        for (i=85;i<=100;i++)
            a[i][1]=b[i][1]=4;

        Min=Max=a[x][1]*n;
        Min=MMin(dfs_min(x*n,n),Min);
        Max=MMax(dfs_max(x*n,n),Max);
        printf("%.4lf %.4lf\n",Min/n,Max/n);
    }
    return 0;




}

POJ 4968 DP||记忆化搜索,布布扣,bubuko.com

POJ 4968 DP||记忆化搜索

原文：http://blog.csdn.net/u011932355/article/details/38704037