[HAOI2006]均分数据

题解

今天下午刚学了模拟退火

借这个题来总结下模拟退火的要注意的问题吧

1 : \(eps\)不要设的太大

2 : 初温\(T\)在2000左右就差不多可以了

3 : 注意题目要求是要求最大值还是最小值,当x<0时\(exp(x)\)的取值范围才是\(0~1\)

4 : 可以在退完火以后再单独从当前最优答案下进行微调

5 : 可以进行多次退火

然后这题就是每次退火就是随机交换序列中的两个数,对序列DP一下就好了

题解

#include<ctime>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<algorithm>

const int M = 25 ;

const int N = 8 ;

const double INF = 1e50 ;

const double EPS = 1e-3 ;

using namespace std ;

int n , m ;

int val[M] , e[M] ;

double f[N][M] , p[M] , Sum[M] ;

double bax , Ans = INF ;

inline double Rand() {

	return (double)((rand() % 101) / 100.0) ;

}

inline double F() {

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

	    for(int j = 0 ; j <= n ; j ++) f[i][j] = INF ;

	f[0][0] = 0 ;

	for(int i = 1 ; i <= n ; i ++) Sum[i] = Sum[i - 1] + p[i] ;

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

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

	        for(int k = i - 1 ; k < j ; k ++)

	            f[i][j] = min(f[i][j] , f[i - 1][k] + (Sum[j] - Sum[k] - bax) * (Sum[j] - Sum[k] - bax)) ;

	if(f[m][n] < Ans) {

		Ans = f[m][n] ;

		for(int i = 1 ; i <= n ; i ++) e[i] = p[i] ;

	}

	return f[m][n] ;

}

inline void Solve() {

	for(int i = 1 ; i <= n ; i ++) p[i] = e[i] ;

	double T = 2000 , W = 0.98 ;

	double NowAns , PreAns , dlt ;

	while(T > EPS) {

		PreAns = F() ;

		int a = rand() % n + 1 , b = rand() % n + 1 ;

		while(a == b) b = rand() % n + 1 ;

		swap(p[a],  p[b]) ;

		NowAns = F() ; dlt = NowAns - PreAns ;

		if(exp(-dlt / T) > Rand()) ;

		else  swap(p[a] , p[b]) ;

	    T *= W ;

	}

	for(int i = 1 ; i <= 10000 ; i ++) {

		int a = rand() % n + 1 , b = rand() % n + 1 ;

		while(a == b) b = rand() % n + 1 ;

		swap(p[a] , p[b]) ;

		F() ;

		swap(p[a] , p[b]) ;

	}

}

int main() {

	srand(time(0)) ;

	cin >> n >> m ;

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

		cin >> val[i] ;

		bax += val[i] ;

		p[i] = val[i] ;

	}

	bax /= m ; F() ;

	int Times = 20 ; while(Times--) Solve() ;

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

	return 0 ;

}

巴特西

[HAOI2006]均分数据

题解

1 : \(eps\)不要设的太大

2 : 初温\(T\)在2000左右就差不多可以了

3 : 注意题目要求是要求最大值还是最小值,当x<0时\(exp(x)\)的取值范围才是\(0~1\)

4 : 可以在退完火以后再单独从当前最优答案下进行微调

5 : 可以进行多次退火

题解

最新文章

热门文章