U40620 niiickの还没想好名字的题

给定一个长度为$n$的序列$a_1,a_2...,a_n$

要求将这$n$个数分为$m$组，每组可以有任意多个数，但同一组中的数必须是原序列中连续的一段

求如何分组能使得各组的标准差最小，

即求$$min(\sqrt{\sum_{i=1}2}{m}})$$其中$x_i$为第$i$组数的和，$\overline{x}$为各组数和的平均值

求这个最小值

纪念一下交了19遍（不是因为debug）

U40620 还没想好名字的题-LMLPHP

Solution

我们先考虑这个部分 $\sum_{i = 1}^{m}(x_{i} - \overline{x}) ^ {2}$

设 $dp[i][j]$ 表示考虑前 $i$ 个数，分成 $j$ 个部分的最小值

类似区间$dp$，我们暴力枚举断点计算多分一组，即大区间的答案

状态转移方程见代码

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#include<climits>

#include<cmath>

#define LL long long

#define REP(i, x, y) for(int i = (x);i <= (y);i++)

using namespace std;

int RD(){

    int out = 0,flag = 1;char c = getchar();

    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}

    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

    return flag * out;

    }

const int maxn = 419;

int num, m;

double dp[maxn][maxn], sum[maxn], ave;

int main(){

	num = RD(), m = RD();

	REP(i, 1, num)sum[i] = sum[i - 1] + RD();

	ave = sum[num] / (m * 1.0);

	REP(i, 0, num)REP(j, 0, m)dp[i][j] = 1e19;

	dp[0][0] = 0;

	REP(i, 1, num){

		REP(j, 1, min(i, m)){

			REP(k, 0, i - 1){

				dp[i][j] = min(dp[i][j],

				dp[k][j - 1] + ((sum[i] - sum[k] - ave) * (sum[i] - sum[k] - ave)));

				}

			}

		}

	printf("%.2lf\n", sqrt(dp[num][m] / (double)m));

	return 0;

	}