[NOIP2019] 劃分

• 2020 年 8 月 18 日
• 筆記
• DP, 單調隊列, 序列

題目

題解

首先YY一個最簡單的dp

$dp[i][j]=min(dp[j][k]+(sum[i]-sum[j])^2 (sum[i]-sum[j]>=sum[j]-sum[k])$

$dp[i][j]$表示i為終點，j為上一段起點的最小代價。

上述過程其實就是在i的左端尋找滿足條件的點，然後一一計算代價並取最小值（注意這些點可能不是連續的）

 但其實，我們只要取最右邊的滿足條件的點來更新就行了，證明見下

 我們可以記一個$pre[i]$表示i點上一個區間的終點

這樣我們就有了一個$O(n^2)$ dp

對於每個點i，我們從i往前掃，找到第一個滿足 $(sum[i]-sum[j]>=sum[j]-sum[pre[j])$ 的點j ，則

$dp[i]=dp[j]+(sum[i]-sum[j])^2$

注意到如果一個點j滿足i,那麼它肯定滿足i+1,

如果不滿足i,也可能滿足i+1

另外，對於 $sum[i]-sum[j]>=sum[j]-sum[pre[j]$

可以變形成 $sum[i]>=2*sum[j]-sum[pre[j]$

那麼可以設一個$d(j)=2*sum[j]-sum[pre[j]$

我們可以用一個單調隊列來維護滿足條件的點

因為我們只需要最右邊滿足條件的點，所以每次i遞增的時候，如果隊頭下一位也滿足條件，就把隊頭踢掉（因為下一位肯定比隊頭更右）

然後用隊頭更新這一位的dp值

然後把這一位從隊尾插入，並把前面d值大於它的點全部刪除

這樣就可以做到$O(n)$了

程式碼

這個是88分的，100分的要寫高精，但正確性是有的。

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
#define N 4*(int)1e7+10
int sum[N],pre[N],q[N],dp[N],l=1,r=0;
#define val(a) (2*sum[a]-sum[pre[a]])
signed main()
{
	int n,type;
	cin>>n>>type;
	for(int i=1;i<=n;i++)
	{
		int a;
		scanf("%lld",&a);
		sum[i]=sum[i-1]+a;
	}
	q[++r]=0;
	for(int i=1;i<=n;i++)
	{
		while(l<r&&val(q[l+1])<=sum[i]) l++;
		pre[i]=q[l];
		dp[i]=dp[pre[i]]+(sum[i]-sum[pre[i]])*(sum[i]-sum[pre[i]]);
		while(l<=r&&val(i)<=val(q[r])) r--;
		q[++r]=i;
	}
	cout<<dp[n];
}