[CF 319C] Kalila and Dimna in the Logging Industry

題目

洛谷

思路

考慮 $dp[i]$ 爲砍掉第 $i$ 棵樹的最小代價，因爲 $b[n]=0$，所以目的是求 $dp[n]$

考慮計算 $dp[k]$。因爲 $b_i$ 單調遞減，所以砍掉編號 $>k$ 的樹之後，就不會再回來管 $k$，而是向 $n$ 奮起直追。這一點似乎很多題解裡並沒有考慮。

所以 $dp[k]$ 只會由 $<k$ 的 $dp$ 來轉移，所以我們考慮列舉 $i$，此時 $dp[k]=\min(dp[i]+b[i]*a[k])$。於是得到了一個 $O(n^2)$ 的樸素 $\tt dp$

考慮優化決策時間複雜度。對於前置決策 $i,j$且$i<j$，當前位置 $k$，該從哪裏轉移過來。對於選擇 $i$ 的條件爲 $dp[i]+b[i]*a[k]<dp[j]+b[j]*a[k]$

移項得到：$\frac{dp[i]-dp[j]}{b[j]-b[i]}>a[k]$

顯然的斜率優化，單調佇列維護即可。

Code：

LL a[MAXN], b[MAXN], dp[MAXN];
deque<LL> Q;
DB Getk(LL i,LL j)
{
	return (dp[i] - dp[j] + 0.0) / (b[j] - b[i]);
}
int main()
{
	LL n;
	read( n );
	for (Int i = 1; i <= n; ++ i)
		read( a[i] );
	for (Int i = 1; i <= n; ++ i)
		read( b[i] );
	Q.push_front( 1 );
	for (Int i = 2; i <= n; ++ i)
	{
		while (Q.size() > 1)
		{
			LL t1 = Q.front();
			Q.pop_front();
			LL t2 = Q.front();
			Q.pop_front();
			if (Getk(t1, t2) > a[i])
			{
				Q.push_front( t2 ); 
				Q.push_front( t1 );
				break;
			}
			else Q.push_front( t2 );
		}
		LL j = Q.front();
		dp[i] = dp[j] + b[j] * a[i];
		while (Q.size() > 1)
		{
			LL t1 = Q.back();
			Q.pop_back();
			LL t2 = Q.back();
			Q.pop_back();
			if (Getk(t1, i) > Getk(t2, t1))
			{
				Q.push_back( t2 );
				Q.push_back( t1 );
				break;
			}
			else Q.push_back( t2 );  
		}
		Q.push_back( i ); 
	}
	printf("%lld", dp[n]);
	return 0;
}