hdu 2899 Strange fuction——模拟退火

时间:2021-06-03 05:50:02

题目:http://acm.hdu.edu.cn/showproblem.php?pid=2899

还可三分。不过只写了模拟退火。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ctime>
#include<cmath>
#include<cstdlib>
#define db double
using namespace std;
const int nx[]={,,,,,},c[]={,,,,,};
const db dc=0.997,eps=1e-;
int T;
db y,ans,px;
db pw(db x,int k){db ret=;while(k){if(k&)ret*=x;x*=x;k>>=;}return ret;}
db calc(db x)
{
db ret=;
for(int i=;i<=;i++)ret+=c[i]*pw(x,nx[i]);
ret-=y*x; return ret;
}
db gtrd(db T){return (rand()*-RAND_MAX)*T;}
void SA(db T)
{
db x0=px,pr=ans,x,cr;
while(T>eps)
{
x=x0+gtrd(T); if(x>)x=; if(x<)x=; cr=calc(x);
if(cr<pr||exp((cr-pr)/T)*RAND_MAX<rand())
{
if(cr<ans)ans=cr,px=x;
x0=x;pr=cr;
}
T*=dc;
}
}
int main()
{
srand(time());
scanf("%d",&T);
while(T--)
{
scanf("%lf",&y);
px=;ans=calc(px);
for(int i=;i<=;i++)SA();
printf("%.4lf\n",ans);
}
return ;
}