Description
Solution
这道题转换一下模型其实就是有很多个带权向量，然后给你一个矩形，给每个向量加一个系数，使得长宽都不超过矩形且权值和最大。 很容易就可以证明出来只需要两个向量就可以了，如果有第三个有系数的，那么就说明这种情况的时候第三个更优，那么还不如直接用第三个替换掉一个。 那么我们现在知道了只用选两个，那么我们该怎么去做这道题？ 首先肯定要
n2
的去枚举，然后我们知道了两个向量之后，就需要列方程了。
y=min(HP−x∗a[i]a[j],MP−x∗b[i]b[j])c[j]+x∗∗c[i]
设x为i向量的系数，然后y是权值和。 那么现在有两种情况，一个是min左边的小，另一个是min右边的小。 那么我们可以分别考虑一下，可以把min左边的和右边的分别抽出来。 当
HP−x∗a[i]a[j]<MP−x∗b[i]b[j]
的时候就会选左边 此时分界点
x′=MPa[j]−HPb[j]b[i]a[j]−b[j]a[i]
当x<=x’的时候，
y=(c[i]−a[i]∗c[j]a[j])x+c[j]∗HPa[j]
当x>=x’的时候，
y=(c[i]−b[i]∗c[j]b[j])x+c[j]∗MPb[j]
因为现在考虑必须选i向量的情况，所以
lim<=min(MPb[i],HPa[i])
如果当前要选则的范围不在lim范围内，那么就不能选。 对于上面y的等式，无论哪边小，最优值都是x’,因为要考虑的是当前选择i向量的最优情况，都必须在斜率的正负性倾向于i向量的方向选择，否则以i向量为主体就没有意义了，这个自己对着上面的斜率分析一下就好了。
Code
using namespace std;
const
int maxn=
2007;
typedef double db;
int i,j,l,t,n,
m,cas,w1,w2;
db a[maxn],b[maxn],c[maxn],H,M,an[maxn],ans,
x,xx,
y,k,bb,lim,an1,an2;
int main(){
freopen(
"terraria.in",
"r",stdin);
freopen(
"terraria.out",
"w",stdout);
for(scanf(
"%d",&cas);cas;cas--){
scanf(
"%d",&n);
scanf(
"%lf%lf",&H,&M);
fo(i,
1,n)scanf(
"%lf",&a[i]);fo(i,
1,n)scanf(
"%lf",&b[i]);fo(i,
1,n)scanf(
"%lf",&c[i]);
ans=an1=an2=
0;w1=w2=
0;memset(an,
0,sizeof(an));
fo(i,
1,n){
lim=min(H/a[i],M/b[i]);
y=lim
*c[i];
if(
y>ans){
ans=
y;w1=i,w2=
0;an1=lim,an2=
0;
}
fo(j,i+
1,n){
x=(M
*a[j]-H
*b[j])/(b[i]
*a[j]-b[j]
*a[i]);
k=c[i]-a[i]/a[j]
*c[j],bb=H
*c[j]/a[j];
if(
x<
0)
continue;
if(
x<lim){
y=
x*k+bb,xx=
x;
if(
y>ans){
ans=
y;w1=i,w2=j;an1=xx,an2=(H-xx
*a[i])/a[j];
}
}
x=(M
*a[j]-H
*b[j])/(b[i]
*a[j]-b[j]
*a[i]);
if(
x>lim)
continue;
k=c[i]-b[i]/b[j]
*c[j],bb=M
*c[j]/b[j];
y=k
*x+bb,xx=
x;
if(
y>ans){
ans=
y;w1=i,w2=j;an1=xx,an2=(M-xx
*b[i])/b[j];
}
}
}
an[w1]=an1,an[w2]=an2;
printf(
"%.10lf\n",ans);
fo(i,
1,n)
printf(
"%.10lf ",an[i]);
printf(
"\n");
}
}
