首页 > 代码库 > [hdu2899]Strange fuction

[hdu2899]Strange fuction

2024-09-15 03:02:00   207人阅读

来自FallDream的博客，未经允许，请勿转载，谢谢。

题意：T组数据，每次给定y，求F(x) = 6 * x^7+8*x^6+7*x^3+5*x^2-y*x (0 <= x <=100) 的最小值  T<=100

 

这题貌似是有正常解法的，就是求导之后二分 然而我不会求导 所以呢  上模拟退火

模拟退火呢 大概是说我有一个初始温度，并且以一定的比率衰减。对于每一个状态，向外扩展状态(温度越大扩展范围越大)，如果它比目前的状态更优，那么就选择它，不然，以一定的比率接受它(显然答案越劣这个比率越小).

然后时间不会很卡，可以多退火几次，比较稳健，但是它的常数还是挺大的233...

#include<iostream>#include<cstdio>#include<ctime>#include<cmath>#include<algorithm>#define INF 1e18#define T 100#define delta 0.98#define eps 1e-8#define IT 5using namespace std;int qq;double ans;inline double calc(double x,double y){    double sq=x*x,cube=x*x*x;    return 6*cube*cube*x+8*cube*cube+7*cube+5*sq-y*x;}inline double Ran(){return (double)rand()/(double)RAND_MAX;}bool check(double x){return x+eps>0&&x<100+eps;}double search(double y){    double x=Ran()*100,res=calc(x,y),t=T;    while(t>eps)    {        for(int j=1;j<=IT;j++)        {            double nx=x+(rand()&1?1:-1)*Ran()*t;            if(check(nx))            {                double th=calc(nx,y);                if(th<res||Ran()>=exp(-th/res)) res=th,x=nx;            }        }        t*=delta;    }    return res;}int main(){    srand(20170415U);    for(cin>>qq;qq;--qq)    {        double y;ans=INF;        scanf("%lf",&y);        for(int i=1;i<=IT;i++)            ans=min(ans,search(y));        printf("%0.4lf\n",ans);    }    return 0;}

 

[hdu2899]Strange fuction


联系
我们