[SDOI2016]征途
题意
题解
DP方程很好推
令dp i,j 表示前I份分到J段
对于一个i,该方程有决策单调性(二次函数)
分治优化即可
#include<bits/stdc++.h> using namespace std; #define ll long long #define re register inline ll read() { ll f = 1,x = 0; char ch; do { ch = getchar(); if(ch == '-') f = -1; }while(ch<'0'||ch>'9'); do { x = (x<<3) + (x<<1) + ch - '0'; ch = getchar(); }while(ch>='0'&&ch<='9'); return f*x; } const int MAXN = 3000 + 10; int n,m; ll d[MAXN]; ll dp[MAXN][MAXN]; ll ans; inline void solve(int l,int r,int L,int R,int x) { if(l>r||L>R) return; int mid = (l+r)>>1,k = 0; dp[x][mid] = 1LL<<60; for(int i=L;i<=R&&i<mid;i++) { ll cur = dp[x-1][i] + (d[mid] - d[i]) * (d[mid] - d[i]); if(cur < dp[x][mid]) dp[x][mid] = cur,k = i; } solve(l,mid-1,L,k,x);solve(mid+1,r,k,R,x); } int main() { n = read(),m = read(); for(re int i=1;i<=n;i++) d[i] = read(),d[i]+=d[i-1]; for(re int i=1;i<=n;i++) dp[1][i] = d[i] * d[i]; for(re int i=2;i<=m;i++) solve(1,n,0,n,i); cout << dp[m][n] * m - d[n] * d[n] << endl; }