题解 P1115 【最大子段和】

· · 题解

模拟退火

DP太无聊了我要用模拟退火来做这道题概念见原理部分
设定初温T,终温eps,降温系数a,退火次数fire
每次退火开始就重置温度t,随机生成一个子段作为初始解

考虑如何生成新方案

根据题意有4个操作

  1. 左移子段左端点
  2. 右移子段左端点
  3. 左移子段右端点
  4. 右移子段右端点

我们随机一个操作,再随机一下移动的距离dis
dis的范围与t成正比效果最好
设alpha={dis/t(dis>=t),dis*t(dis<t)}
然后判断新子段是否合法,合法继续
再判断新解是否更优（新子段和-原子段和delta>0）
为了快速计算字段和我们需要前缀和优化不会自己百度
设接受新解的概率p=exp(-Δ/t)且随温度t的降低而降低
如果更优显然p>1一定接受
如果更劣0<p<1一定概率接受
每次操作后降温t=t*a

原理

一开始温度很高以较高概率接受劣解,很容易跳出局部最优解
随着温度降低解越来越稳定，最后稳定在局部最优解
当然只有一定概率是全局最优解
我们可以运行多次(重新烧热再退火)取每次结果的最大值

关于参数和复杂度

一般根据题目数据范围取a=0.95-0.99,T=10^3-10^5,eps=10^{-5}-10^{-7}
时间复杂度只与参数有关与问题规模无关 每次生成新解O(1)
每次退火生成新解的次数x=O(log_a{eps/T})
总时间复杂度O(firelog_a{eps/T})
一般根据运行时间和正确性调参如果时间充裕可以适当开大

总结

补充个坑点就是linux的RAND_MAX是2^{31}-1而windows是2^{15}-1
我RE了好多次所以在windows下可以这么写

#define rand_windows() (rand()*16384ll+(rand()>>1))
#define RAND_MAX_windows 268435456.0

然后在程序里用,但在提交时一定要改回去
因为是普及-的题所以尽量通俗但可能牺牲严谨性,有疑问的可以百度
不会正解的可以用这个骗很多分洗把脸或多交几发就AC了附上我的代码
新人第一篇题解管理员求过

#include<bits/stdc++.h>
#define rand_windows() (rand()*16384ll+(rand()>>1))
#define rand_max_windows 268435456.0
using namespace std;
const double A=0.98,T=2e4,eps=1e-5;const int fire=15000,alpha=1;
int n,a[200001],current[2];long long s[1000001],ans=-0x7fffffffffffffff;
int main()
{
    scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]),s[i]=s[i-1]+a[i];
    for(int k=1;k<=fire;k++){
        srand(rand()+clock());double t=T,p;long long res,dis,delta;short operation;
        for(int i=0;i<2;i++)current[i]=rand()%n+1;sort(current,current+2);res=s[current[1]]-s[current[0]-1];
        while(t-eps>0){
            t*=A;operation=rand()%4;dis=rand()*1ll*t*alpha/RAND_MAX+1;p=1.0;
            switch(operation){
                case 0:{if(current[0]-dis<1)break;delta=s[current[0]-1]-s[current[0]-dis-1];if(delta<=0)p=rand()/(double)RAND_MAX;if(p<exp((double)delta/t))res+=delta,current[0]-=dis;break;}
                case 1:{if(current[0]+dis>current[1])break;delta=s[current[0]-1]-s[current[0]+dis-1];if(delta<=0)p=rand()/(double)RAND_MAX;if(p<exp((double)delta/t))res+=delta,current[0]+=dis;break;}
                case 2:{if(current[1]-dis<current[0])break;delta=s[current[1]-dis]-s[current[1]];if(delta<=0)p=rand()/(double)RAND_MAX;if(p<exp((double)delta/t))res+=delta,current[1]-=dis;break;}
                case 3:{if(current[1]+dis>n)break;delta=s[current[1]+dis]-s[current[1]];if(delta<=0)p=rand()/(double)RAND_MAX;if(p<exp((double)delta/t))res+=delta,current[1]+=dis;break;}
            }
        }
        if(res>ans)ans=res;
    }
    printf("%lld",ans);
    return 0;
}