ToB企服应用市场:ToB评测及商务社交产业平台

标题: P5665 [CSP-S2019] 划分 [打印本页]

作者: 卖不甜枣 时间: 2024-8-1 20:43
标题: P5665 [CSP-S2019] 划分
思路：

首先求出 $a$ 的前缀和数组 $s$。
考虑动态规划，令 $dp_{i,j}$ 表示以 $i$ 末端，末端有 $j$ 个为一组的最小答案，则状态转移方程为：

\[dp_{i,j} = \min [s_{i-j}-s_{i-j-k} \le s_i - s_{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}$，那么状态转移方程为：

\[dp_{i,j} = (s_i - s_{i-j})^2 + \min\limits_{l=1}^k dp_{i-j,l}\]
后面的一串可以提前前缀预处理好，现在的复杂度在求 $k$ 上，留意到 $s_{i,j} - s_{i-j-k}$ 是单调的，那么直接二分即可。
时间复杂度优化至 $O(N^2 \log N)$。
$O(N^2 \log N)$ 代码[code]#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

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)