[NOIP2019] 劃分
題目
題解
首先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]; }