试题 算法训练 Remember the A La Mode
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
Hugh Samston经营着一个为今年的ICPC世界总决赛的参与者提供甜点的餐饮服务。他将会提供上面有冰激凌的饼片。为了满足不同的需求，他准备了许多不同的饼片和冰激凌。
Hugh希望以一份饼片上一份冰激凌的方式来提供甜点。然而，作为一个商人，他希望能赚到尽可能多的钱。他知道不同种类的饼片和冰激凌组合的价格，也知道那些冰激凌和那些饼片不能组合在一起。
Hugh想根据每种饼片和冰激凌的数量，以及之前提到的不同组合的情况，确定他能获得的利润的范围。
输入格式
测试数据的输入一定会满足的格式 。
输入的第一行包含两个整数P, I，分别表示饼片和冰激凌的种类数。
接下来一行包含P个整数，表示每种类型饼片的数量 。
接下来一行包含I个整数，表示每种类型冰激凌的数量。
接下来P行，每行包含I个实数，表示每种类型饼片和冰激凌组合的结果。
如果这种饼片和这种冰激凌可以组合，则为一个(0,10)的实数，表示这种组合的收益。
否则，则为-1,表示这两种之间不能组合。
输出格式
输出一行，以"(最小收益) to (最大收益)"的方式输出利润的范围。
请注意：所有的饼片和冰激凌都必须用完。
样例输入
2 3
40 50
27 30 33
1.11 1.27 0.70
-1 2 0.34
样例输出
91.70 to 105.87
数据规模和约定
0 < P,I <= 50，每种类型饼片或冰激凌数量不超过100。
#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;
#define max_size 110
typedef struct
{
int n,m;
float value;//n为饼干的序号,m为冰激凌序号，value为组合的价值
}zh;
long double res=0,max_res=0,min_res=0;
long sum=0;//总份数
float rule(zh a,zh b)//从大到小排序，求最大收益用
{
return a.value>b.value;
}
float rule1(zh a,zh b)//从小到大排序，求最小收益用
{
return a.value<b.value;
}
void f(int bk[],int ice[],zh a[],int b,int c)//b排序好后的第几个数 c已完成配对数
{
if(c>=sum);
else if(a[b].value<0) f(bk,ice,a,b+1,c);
else if(bk[a[b].n]==0||ice[a[b].m]==0) f(bk,ice,a,b+1,c);
else
{
if(bk[a[b].n]<ice[a[b].m])
{
res=res+a[b].value*bk[a[b].n];
c=c+bk[a[b].n];
ice[a[b].m]=ice[a[b].m]-bk[a[b].n];
bk[a[b].n]=0;
f(bk,ice,a,b+1,c);
}
else
{
res=res+a[b].value*ice[a[b].m];
c=c+ice[a[b].m];
bk[a[b].n]=bk[a[b].n]-ice[a[b].m];
ice[a[b].m]=0;
f(bk,ice,a,b+1,c);
}
}
}
int main()
{
int P,I;
cin>>P>>I;
int i,j,num_bk[max_size]={0},num_ice[max_size]={0};
int bk[max_size],ice[max_size];
zh combination[3000];
for(i=1;i<=P;i++)
{
cin>>num_bk[i];
bk[i]=num_bk[i];
sum=sum+num_bk[i];
}
for(i=1;i<=I;i++)
{
cin>>num_ice[i];
ice[i]=num_ice[i];
}
int a;
for(i=1,a=0;i<=P;i++)
{
for(j=1;j<=I;j++)
{
cin>>combination[a].value;
combination[a].n=i;
combination[a++].m=j;
}
}
sort(combination,combination+a,rule);//给收益排序
f(num_bk,num_ice,combination,0,0);
max_res=res;
res=0;
sort(combination,combination+a,rule1);
f(bk,ice,combination,0,0);
min_res=res;
cout<<fixed<<setprecision(2)<<(long double)min_res<<" to "<<(long double)max_res;//设置输出格式为保留小数点后两位
return 0;
}
//我这么做只得了20分，我找不到问题在哪