P11188 题解

· · 题解

1. 题目分析

这是一篇模拟退火题解。
我第一眼看到这道题就知道这道题是动态规划或者贪心。
但是我太菜了推不出式子，于是只能另辟蹊径。

2. 题目做法

仔细观察数据范围，v 最大只有 10^5，故最优策略保留的数必定不超过 5 个。
我们首先想到暴力搜索，但搜索的方案数实在是太过庞大，时间复杂度是不允许的。我们发现每次方案变动对答案的影响都不是很大，故不难想此题的所有方案的值是一个连续的多峰函数，于是我们可以考虑用模拟退火来解决此题。
所以我们可以随机这 5 个点的位置，若有两个点位置重合，说明此时我们只选 4 个点，这样就可以处理选 5 个以下点的情况了。
若 n 的位数小于等于 5 时，我们还需要先算一次一个数都不保留时的值，这是显然的。
我们用一个 to 数组记录我们要保留哪几个位置的数。在退火时，每次我们随机两个值 x 和 y，x 表示我们要改变的 to 数组的下标，y 表示将此下标的 to 数组的值改成什么。
有一些优化我放代码的注释里了，此题时间限制较宽裕，不加优化应该也能过。

3. 代码

#include<bits/stdc++.h>
#define r() rand()
#define R(l,r) ((double)rand()/RAND_MAX*(r-l))
#define ll long long
using namespace std;
const int N=100010;
inline int read()
{
    int x=0;
    char c=getchar();
    while(c<'0'||c>'9')
        c=getchar();
    while(c>='0'&&c<='9')
        x=(x<<1)+(x<<3)+c-'0',c=getchar();
    return x;
}
int C,t;
char c[N];
int n,v[10],a[N];
double T,dt;
int to[7],have[N],num;
ll sum,ans,tt,now,fu;
inline ll change(int x,int y)
{
    have[to[x]]==1?sum+=v[a[to[x]]]:1;
    !have[y]?sum-=v[a[y]]:1;
    to[x]=y;
    num=a[to[1]];
    for(int i=2;i<=5;i++)
        to[i]!=to[i-1]?num=(num<<1)+(num<<3)+a[to[i]]:1;
    tt=sum+num;
    tt<ans?ans=tt:1;
    return tt;
}
void SA()
{
    T=1e5;
    sum=0;
    for(int i=1;i<=n;i++)
        sum+=v[a[i]];
    ans=sum;
    for(int i=1;i<=5;i++)
        to[i]=r()%n+1,have[to[i]]++;
    sort(to+1,to+6);
    num=a[to[1]],sum-=v[a[to[1]]];
    for(int i=2;i<=5;i++)
        to[i]!=to[i-1]?num=(num<<1)+(num<<3)+a[to[i]],sum-=v[a[to[i]]]:1;
    now=sum+num;
    ans=min(ans,now);
    while(T>1e-7)
    {
        //最好让 to 数组保持升序，这样每次改变都不用让 to 数组重新排序了 
        int x=rand()%5+1,y=r()%(to[x+1]-to[x-1]+1)+to[x-1];
        if(to[x]==y)//此时不用进行更改 
            continue;
        int g=to[x],numg=num;
        ll sumg=sum;
        fu=change(x,y);
        dt=now-fu;
        if(exp(dt/T)>R(0,1))
            now=fu,have[g]--,have[y]++;
        else
            to[x]=g,sum=sumg,num=numg;
        T*=0.9999;
    }
    for(int i=1;i<=5;i++)
        have[to[i]]--;
}
int main()
{
    C=read(),t=read();
    to[0]=1;
    while(t--)
    {
        scanf("%s",c+1);
        n=strlen(c+1);
        to[6]=n;
        for(int i=1;i<=n;i++)
            a[i]=c[i]-'0';
        for(int i=1;i<=9;i++)
            v[i]=read();
        if(n==1)//特判，否则我的程序会进死循环 
        {
            printf("%d\n",min(a[1],v[a[1]]));
            continue;
        }
        SA();
        printf("%lld\n",ans);
    }
    return 0;
}