yukicoder : No.453 製薬会社

いい加減線形計画法をちゃんと勉強した方がいいのかしら。
http://yukicoder.me/problems/no/453

問題

薬品C,Dを使い製品A,Bを作る。
Aを1kg作るにはC,Dが3/4kg, 1/4kg必要である。
Bを1kg作るにはC,Dが2/7kg, 5/7kg必要である。

A,Bはそれぞれ1kgで1000円・2000円で売れる。
A,Bの生産・販売量およびC,Dの使用量は整数でなくてもよい。
C,Dを最適に用いる場合、売値の最大値を求めよ。

解法

Aを生産量を決めれば、残りの薬品で作れるBの最大量も決まる。
また、Aの生産量に対し売値は上に凸な関数となる。
よって三分探索で解ける。

double C,D;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>C>>D;
	
	double L=0,R=min(C/0.75,D/0.25);
	
	FOR(i,200) {
		double M1=(L*2+R)/3;
		double M2=(L+R*2)/3;
		double r1= M1*1000 + min((C-M1*0.75)/(2.0/7.0),(D-M1*0.25)/(5.0/7.0))*2000;
		double r2= M2*1000 + min((C-M2*0.75)/(2.0/7.0),(D-M2*0.25)/(5.0/7.0))*2000;
		if(r1>r2) R=M2;
		if(r1<r2) L=M1;
		if(r1==r2) L=M1,R=M2;
	}
	double ret = L*1000 + min((C-L*0.75)/(2.0/7.0),(D-L*0.25)/(5.0/7.0))*2000;
	_P("%.12lf\n",ret);
	
}

まとめ

単体法とか線形計画法、名前は聞くけど理解してない。
競プロだとDiv1 Hardで稀に出るイメージだけど、一度理解しておいた方がいいのだろうか？