深圳网站营销seo电话,注册送38元的游戏网站,四川建设银行手机银行下载官方网站下载,网站建设准备工作正题
题目链接:https://loj.ac/problem/2035 题目大意 nnn个数字分成mmm段#xff0c;要求方差最小。 解题思路
首先方差的公式∑i1n(xi−∣x∣)2\sum_{i1}^n(x_i-|x|)^2i1∑n(xi−∣x∣)2 其中∣x∣|x|∣x∣是不变的#xff0c;定义w∣x∣w|x|w∣x∣ 设fi,jf_{i,j}fi,…正题
题目链接:https://loj.ac/problem/2035 题目大意
nnn个数字分成mmm段要求方差最小。 解题思路
首先方差的公式∑i1n(xi−∣x∣)2\sum_{i1}^n(x_i-|x|)^2i1∑n(xi−∣x∣)2 其中∣x∣|x|∣x∣是不变的定义w∣x∣w|x|w∣x∣ 设fi,jf_{i,j}fi,j表示已经分到第iii段到第jjj个时的最小方差和。
做前缀和si∑j1iais_i\sum_{j1}^ia_isi∑j1iai 之后有fk,imin{fk−1,j(si−sj)2w2−2(si−sj)w}f_{k,i}min\{f_{k-1,j}(s_i-s_j)^2w^2-2(s_i-s_j)w\}fk,imin{fk−1,j(si−sj)2w2−2(si−sj)w} 去掉minminmin拆括号 fk,ifk−1,jsi2−2sisjsj2w2−2siwsjwf_{k,i}f_{k-1,j}s_i^2-2s_is_js_j^2w^2-2s_iws_jwfk,ifk−1,jsi2−2sisjsj2w2−2siwsjw fk,i−si2siw2sisj−2sjwfk−1,jsj2f_{k,i}-s_i^2s_iw2s_is_j-2s_jwf_{k-1,j}s_j^2fk,i−si2siw2sisj−2sjwfk−1,jsj2 求fk,if_{k,i}fk,i最小就是fk,i−si2siwf_{k,i}-s_i^2s_iwfk,i−si2siw最小后为了方便 定义Ffk,i−si2siwFf_{k,i}-s_i^2s_iwFfk,i−si2siw F2(si−w)sjfk−1,jsj2F2(s_i-w)s_jf_{k-1,j}s_j^2F2(si−w)sjfk−1,jsj2 然后有若干个决策点(sj,fk−1,jsj2)(s_j,f_{k-1,j}s_j^2)(sj,fk−1,jsj2) 每次有一条直线y2(si−w)xFy2(s_i-w)xFy2(si−w)xF经过某个决策点要求FFF最小 显然因为si−ws_i-wsi−w的单调性和sjs_jsj的单调性我们可以使用单调队列维护一个下凸壳。
时间复杂度O(nm)O(nm)O(nm) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define pow2(x) ((x)*(x))
using namespace std;
const int N3100;
struct node{double x,y;int num;
}q[N];
int n,m;
double s[N],f[N][N];
double slope(node x,node y)
{return (y.y-x.y)/(y.x-x.x);}
int main()
{scanf(%d%d,n,m);for(int i1;in;i)scanf(%lf,s[i]),s[i]s[i]*ms[i-1];double ws[n]/m;for(int i1;in;i)f[1][i]pow2(s[i]-w);for(int k2;km;k){int head1,tail1;q[1](node){s[k-1],f[k-1][k-1]pow2(s[k-1]),k-1};for(int ik;in;i){int z2*(s[i]-w);while(headtailslope(q[head],q[head1])z)head;int pq[head].num;f[k][i]f[k-1][p]pow2(s[i]-s[p]-w);node po(node){s[i],f[k-1][i]pow2(s[i]),i};while(headtailslope(po,q[tail])slope(q[tail-1],q[tail]))tail--;q[tail]po;}}printf(%.0lf,f[m][n]/m);
}
