题解：P2808 [JOI2014 预选赛] 小笼包

Fire_flys · 2025-11-25 16:57:46 · 题解

事先声明：本做法纯属乱搞。

数据这么小，还可以对于某个状态进行模拟，且单次模拟的时间不大，那么模拟退火就可以乱搞一下了。

具体地，我们每次随机扰动，交换序列中任意两个小笼包的顺序，然后进行模拟，以一定几率接受劣解即可。

然后你结合 IOI 的制度，一次不行就多交几次就行了。

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-8,dt=0.995;
const int N=1e2+10;
struct node{
    int d,a,id;
}c[N];
int n,s[N],ans=0;
mt19937 myrand(time(0));
inline int cal(){
    int res=0;
    for(int i=1;i<=n;i++)s[i]=0;
    for(int i=1;i<=n;i++){
        res+=s[c[i].id];
        int minn=max(1,c[i].id-c[i].d);
        int maxn=min(n,c[i].id+c[i].d);
        for(int j=c[i].id-1;j>=minn;j--)s[j]+=c[i].a;
        for(int j=c[i].id+1;j<=maxn;j++)s[j]+=c[i].a;               
    }
    return res;
}
inline void SA(){
    random_shuffle(c+1,c+1+n);
    double T=10000.0;
    int cnt=100,res=0,now=0;
    while(T>eps){
        for(int k=1;k<=cnt;k++){
            int x=myrand()%n+1,y=myrand()%n+1;
            while(x==y)y=myrand()%n+1;
            swap(c[x],c[y]);
            res=cal();
            double delta=res-now;
            //cout<<"delta="<<delta<<"\n";
            if(delta>0){
                now=res;
                ans=max(ans,now);
            }
            else{
                double p=exp(delta/T);
                uniform_real_distribution<double> rand_p(0,1);
                if(rand_p(myrand)<p)now=res;
                else swap(c[x],c[y]);
            }
        }
        T*=dt;
    }
    //cout<<ans<<"\n";
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>c[i].d;
    for(int i=1;i<=n;i++){
        cin>>c[i].a;
        c[i].id=i;
    }
    for(int i=1;i<=5;i++)SA();
    cout<<ans<<"\n";
    return 0;
}