sol

如果已经确定了一个序列，现要求把这个序列分成m个连续段作为答案，那么就可以用一个显而易见的DP

DP显然可以得到当前序列下的最优解。

所以模拟退火瞎JB改一改序列每次DP一下就可以了

据说这题random_shuffle可以AC

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<ctime>

using namespace std;

int n,m,a[25];double s[25],dp[25][10],sum,ans=1e50;

double sqr(double x){return x*x;}

double getdp()

{

	for (int i=1;i<=n;++i) s[i]=s[i-1]+a[i];

	memset(dp,127,sizeof(dp));

	dp[0][0]=0;

	for (int i=1;i<=n;++i)

		for (int j=1;j<=m;j++)

			for (int k=0;k<i;k++)

				dp[i][j]=min(dp[i][j],dp[k][j-1]+sqr(s[i]-s[k]-sum));

	ans=min(ans,dp[n][m]);

	return dp[n][m];

}

double Rand(){return rand()%100000/100000.00;}

void SA(double T)

{

	double now=ans,nw;

	int x,y;

	while (T>1e-3)

	{

		int x=1+rand()%n,y=1+rand()%n;

		if (x==y) continue;

		swap(a[x],a[y]);

		nw=getdp();

		if (nw<now||exp((now-nw)/T)>Rand()) now=nw;

		else swap(a[x],a[y]);

		T*=0.99;

	}

}

int main()

{

	srand(141905+141936);

	scanf("%d %d",&n,&m);

	for (int i=1;i<=n;++i) scanf("%d",&a[i]),sum+=a[i];

	sum/=m;

	getdp();

	SA(1000);

	printf("%.2lf\n",sqrt(ans/m));

	return 0;

}

巴特西

[BZOJ2503][HAOI2006]均分数据

sol

code

最新文章

热门文章