P5665 [CSP-S2019] 划分
思路：首先求出 \(a\) 的前缀和数组 \(s\)。
考虑动态规划，令 \(dp_{i,j}\) 表示以 \(i\) 末端，末端有 \(j\) 个为一组的最小答案，则状态转移方程为：
\ dp_{i-j,k} + (s_i - s_{i-j})^2\]
质朴直接转移是 \(O(N^3)\) 的，可以得到 36pts 的好效果代码就懒的给了。
考虑优化，对于求出最小的一个 \(k\)，使得 \(s_{i-j}-s_{i-j-k} > s_i - s_{i-j}\)，那么状态转移方程为：
\
后面的一串可以提前前缀预处理好，现在的复杂度在求 \(k\) 上，留意到 \(s_{i,j} - s_{i-j-k}\) 是单调的，那么直接二分即可。
时间复杂度优化至 \(O(N^2 \log N)\)。
$O(N^2 \log N)$ 代码#include#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);using namespace std;typedef double db;typedef unsigned long long ull;typedef long long ll;bool Begin;const ll N=5050,INF=4e18;inline ll read(){ ll x=0,f=1; char c=getchar(); while(c'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c
页:
[1]