yukicoder : No.31 悪のミックスジュース

これは実装は短いけど一ひねり必要な問題。
http://yukicoder.me/problems/3

問題

1～N番のN種類のジュースを混ぜたミックスジュースをVリットル作りたい。
各ジュースの１リットル当たりの価格はC[i]である。
各ジュースの使用量はリットル単位でなくてもよいが、購入できるのはリットル単位である。

ここで、原材料表記でウソをつかないため、ミックスジュースにおける各ジュースの使用量P[i]は次の条件を満たさなければならない。

• 全てのジュースを含む。P[i]＞0。
• 各ジュースを含む量は番号順である。P[1]≧P[2]≧P[3]...

Vリットルのジュースを作る最低価格を求めよ。

解法

各ジュースはちょっとは入れないといけないので、先に1リットルずつは固定で購入してしまおう。
残り(V-N)リットルをどう作るかが問題。

ここで、２つ目の条件より、i番目のジュースを1リットル買い足すには1～i番のジュースをすべて１リットル買い足さないといけない。
結果、iリットルのジュースを金額sum(C[1..i])で購入することになる。
逆に考えれば、ジュースのリットル単価はsum(C[1..i])/iとなるので、Vの大半を単価が最小となるiで買えばよい。
ここでiリットルずつ買うと若干過不足が出るので、そこはiリットル未満の購入でつじつまが合うようDPで最小値を求めればよい。

ll N,V;
ll C[102],S[102];

ll co[20900];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>V;
	FOR(i,N) cin>>C[i+1],S[i+1]=S[i]+C[i+1];
	if(V<=N) return _P("%lld\n",S[N]);
	
	V-=N;
	
	x=1;
	for(i=2;i<=N;i++) {
		if(S[i]*x < S[x]*i) x=i;
	}
	for(i=0;i<=min(20200,(int)V);i++) {
		co[i]=1LL<<60;
		if((V-i)%x==0) co[i]=(V-i)/x*S[x];
	}
	for(i=min(20000,(int)V);i>=0;i--) {
		for(j=1;j<=N;j++) co[i]=min(co[i],co[i+j]+S[j]);
	}
	cout<<co[0]+S[N]<<endl;
}

まとめ

どこら辺が悪なのだろう。