Category:BZOJDP/动态规划HAOI乱搞省选专题
Article From:https://www.cnblogs.com/luyouqi233/p/9124366.html

https://www.lydsy.com/JudgeOnline/problem.php?id=2428

https://www.luogu.org/problemnew/show/P2503

N is known as a positive integer: A1, A2, and… An. Now we want to divide them into group M, which makes the data of each group numerical and the most average, that is, the mean variance of each group is the smallest. The formula of mean square deviation is as follows

 

The sigma is a mean square deviation.It is the average of the data and the data of each group, XiThe numeric sum for the data of group I.

We have done a lot of questions like this. First we will expand the mean square deviation formula and find that the answer is small and big is related to sigma (xi^2).

So we can DP… Wait, it looks like this sequence can be taken… DP doesn’t seem to be able to do it.

So we randomly simulated annealing, and randomly exchanged two elements for this sequence each time, then DP check to see if ans could get smaller.

dpThe equation was so simple that I was lazy to write.

#include<cmath>
#include<queue>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long double dl;
const int N=25;
const dl T=3157;
const dl eps=1e-15;
const dl delta=0.998;
inline int read(){
    int X=0,w=0;char ch=0;
    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
    while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
int n,m,a[N],s[N],f[N][10];
dl sum,rms,t,ans=9e18;
inline int sigma(int l,int r){
    return (s[r]-s[l-1])*(s[r]-s[l-1]);
}
inline int suan(){
    memset(f,127,sizeof(f));
    for(int i=1;i<=n;i++){
    s[i]=s[i-1]+a[i];
    f[i][1]=sigma(1,i);
    for(int j=2;j<=min(i,m);j++){
        for(int k=1;k<i;k++){
        f[i][j]=min(f[i][j],f[k][j-1]+sigma(k+1,i));
        }
    }
    }
    return f[n][m];
}
void simulate_anneal(){
    t=T;
    while(t>eps){
    int i=rand()%n+1,j=rand()%n+1;
    swap(a[i],a[j]);
    dl nans=suan();
    dl dans=nans-ans;
    if(nans<ans||rand()<exp(-dans/t)*RAND_MAX)ans=nans;
    else swap(a[i],a[j]);
    t*=delta;
    }
}
int main(){
    srand(19260817);
    n=read();m=read();
    for(int i=1;i<=n;i++)a[i]=read(),sum+=a[i];
    simulate_anneal();
    rms=sum/m;
    ans=sqrt((ans-rms*rms*m)/m);
    printf("%.2Lf\n",ans);
    return 0;
}

+++++++++++++++++++++++++++++++++++++++++++

 +The author of this article: luyouqi233. +

 +Welcome to my blog: http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

Leave a Reply

Your email address will not be published. Required fields are marked *