yukicoder : No.409 ダイエット

横着解法ですいません。
http://yukicoder.me/problems/no/409

問題

初期状態で体重がWキロある。
以後N日の間にそれぞれドーナツを食べるまたは食べないことができる。
i日目にドーナツを食べると体重がD[i]キロ増加する。
逆に食べないと1日でAキロ減少する。
ただしドーナツを食べない日が直前にx日連続している場合、x日目に(B*x)キロ体重が増加する。

最適にドーナツを食べた場合、N日後の体重の最小値を求めよ。

解法

本番中Convex Hull Trickだろうなと思いつつ、うまく式を立てられなかった。
実際想定解はCHTだが、ここでは横着解法で解く。

まずO(N^2)解法は簡単に思いつくだろう。
dp(d,i) := 初期状態からd日目後、直前i日ドーナツを食べていない場合の体重の最小値

ここで、連続してi日ドーナツを食べない場合i日間でB*i*(i+1)/2キロ体重が増加する。
A:Bの比は最大でも10^6:1なので、1000日以上ドーナツを食べずにいると体重の増加分が確実に食べないことによるメリットより多くなる。
よって上記DPはi≦1000の範囲で行えばよい。
するとO(N*√(A/B))のDPで済む。

なお、B==0の場合は一日も食べないことが確実に有利なので、そこだけ注意。

ll N,A,B,W;
int D[303030];

ll from[1200];
ll to[1200];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>B>>W;
	FOR(i,N) cin>>D[i];
	
	if(B==0) return _P("%lld\n",W-A*N);
	
	FOR(i,1200) from[i]=1LL<<60;
	from[0]=W;
	
	FOR(i,N) {
		memset(to,0x3f,sizeof(to));
		FOR(j,1100) {
			// not eat
			to[j+1] = min(to[j+1],from[j]+B*(j+1)-A);
			// eat
			to[0] = min(to[0],from[j]+D[i]);
		}
		swap(from,to);
	}
	cout<<*min_element(from,from+1101)<<endl;
}

まとめ

CHT思いついたものの二乗の項が処理できず困ってしまった。