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

#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> #define fo(i,a,b) for(i=a;i<=b;i++) 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");} }

總結

以上是生活随笔為你收集整理的【GDSOI2017】魔兽争霸 x的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。