[HDU][3696][搜索] Farm Game

题目大意

农场有n种产品，他们之间可以通过牲畜或机械进行加工转化。转化形式为：1单位的产品A可以转化为x单位的产品B，其中x是大于0的实数。另外，每一种产品有不同的售价，第i种产品的单价为Pi。现给出若干初始产品，请将其经过适当加工转化，然后全部卖出，使得最终获利最大。

思路

核心思想是利用深搜作预处理求出每种产品1单位可以换取的最大钱数。

代码

#include
#include
#include
using namespace std;
#define MAXSIZE 10000
int n,m;
double price[MAXSIZE+1],origin[MAXSIZE+1],mark[MAXSIZE+1];
//price[]存储每种产品的单位售价。 
//origin[]存储每种产品的数量。 
//mark[]存储每种产品1单位能换取的最大钱数。 
vector< pair > map[MAXSIZE+1];
//pair<产品编号，换取的数量>
//map[]用于存储产品间的转换关系。 
void init()
//初始化 
{
    for(int i=1;i<=n;i++)
    {
        price[i]=0;
        origin[i]=0;
        mark[i]=0;
        map[i].clear();
    }
}
void input()
//输入 
{
    for(int i=1;i<=n;i++)
        scanf("%lf%lf",&price[i],&origin[i]);
    scanf("%d",&m);
    for(int i=0;i(now,b));
                pre=now;
            }
            else
                scanf("%lf",&b);
    }
}
double dfs(int x)
//dfs(x)的返回值为编号为x的产品1单位所能换取的最大钱数。
//深搜进行的同时，对mark[]进行了赋值。 
{
    if(mark[x])
        return mark[x];
    int size=map[x].size();
    if(size==0)
        return mark[x]=price[x];
    double max=price[x];
    for(int i=0;itemp?max:temp;
    }
    return mark[x]=max;
}
int main()
{
    while(scanf("%d",&n)&&n)
    {
        init();
        input();
        for(int i=1;i<=n;i++)
            dfs(i);
        double sum=0;
        for(int i=1;i<=n;i++)
            sum+=origin[i]*mark[i];
        printf("%.2lf\n",sum);
    }
}

发表回复取消回复