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 感谢分享，学习下。 前排留名，哈哈哈 用心讨论，共获提升！ 感谢分享，下载保存了，貌似很强大 收藏一下 不知道什么时候能用到 这个有用。 感谢分享 yyds。多谢分享 谢谢楼主提供！ 收藏一下 不知道什么时候能用到 谢谢分享，辛苦了 谢谢楼主提供！ 分享、互助 让互联网精神温暖你我 感谢分享 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 感谢分享，学习下。 分享、互助 让互联网精神温暖你我 感谢，下载保存了 前排留名，哈哈哈
页:
[1]
2