首页 > 其他 > 详细

[BJOI2019]奥术神杖

时间:2019-04-28 10:15:49      阅读:107      评论:0      收藏:0      [点我收藏+]

https://www.luogu.org/problemnew/show/P5319

题解

首先观察我们要求的答案的形式:
\[ \biggl(\prod V_i \biggr)^x\ \ \ x=\frac{1}{c} \]
这个东西貌似还不能最优化,根据套路论,把这个东西整体取个\(ln\),于是就变成了:
\[ ln\biggl(\biggl(\prod V_i \biggr)^x\biggr)=\frac{1}{x}\sum ln(V_i) \]
然后这个东西就可以分数规划了,验证的话跑个dp就好了。

有一点就是必须匹配至少一个串,题解好像在状态里加了一维0/1表示有没有匹配到一个串,我是偷懒直接加了个\(eps\)

代码

#include<bits/stdc++.h>
#define N 1509
using namespace std;
typedef long long ll;
const double eps=1e-5;
queue<int>q;
double dp[N][N],cnt[N],mx[N],w;
int tot,ch[N][10],f[N],n,m,tag1[N][N],tag2[N][N];
char s[N],s1[N];
inline ll rd(){
    ll x=0;char c=getchar();bool f=0;
    while(!isdigit(c)){if(c=='-')f=1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;  
}
inline void ins(int len){
    int now=0;
    for(int i=1;i<=len;++i){
        if(!ch[now][s1[i]-'0'])ch[now][s1[i]-'0']=++tot;
        now=ch[now][s1[i]-'0'];
    }
    mx[now]+=w;cnt[now]++;
}
inline void build(){
    for(int i=0;i<10;++i)if(ch[0][i])q.push(ch[0][i]);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=0;i<10;++i){
            if(ch[u][i])f[ch[u][i]]=ch[f[u]][i],mx[ch[u][i]]+=mx[ch[f[u]][i]],
              cnt[ch[u][i]]+=cnt[ch[f[u]][i]],q.push(ch[u][i]);
            else ch[u][i]=ch[f[u]][i];
        }
    }
}
inline bool check(double mid){
    memset(dp,-0x3f,sizeof(dp));
    dp[0][0]=0;
//  printf("%.2lf   ",mid);
    for(int i=1;i<=n;++i){
//      printf(" ");
        for(int j=0;j<=tot;++j){
            if(s[i]=='.')
            for(int k=0;k<10;++k){
                int x=ch[j][k];
                double xx=dp[i-1][j]+mx[x]-mid*cnt[x];
    //          printf("%.2lf ",xx);
                if(xx>dp[i][x]){
                    dp[i][x]=xx;
                    tag1[i][x]=k;tag2[i][x]=j;
                }
            }
            else{
                int x=ch[j][s[i]-'0'];
                double xx=dp[i-1][j]+mx[x]-mid*cnt[x];
                if(xx>dp[i][x]){
                    dp[i][x]=xx;
                    tag2[i][x]=j;
                }
            }
        }
    }
//  puts("");
    for(int j=0;j<=tot;++j)if(dp[n][j]>eps)return 1;
    return 0;
}
void dfs(int len,int now){
    if(!len)return;
    if(s[len]=='.')s[len]=tag1[len][now]+'0';
    dfs(len-1,tag2[len][now]);
//  cout<<now<<" ";printf("%.2lf  ",dp[len][now]);
}
int main(){
    n=rd();m=rd();
    double l=0,r=0;
    scanf("%s",s+1);
    for(int i=1;i<=m;++i){
        scanf("%s",s1+1);w=log((double)rd());
        r=max(r,w); 
        ins(strlen(s1+1));
    }
    r+=1000;
    build();    
    while(l+eps<r){
        double mid=(l+r)/2;
        if(check(mid))l=mid;
        else r=mid;
    }
//  printf("%.2lf\n",l);
    check(l);
    for(int j=0;j<=tot;++j)if(dp[n][j]>eps){
        dfs(n,j);break;
    }
    printf("%s",s+1);
    return 0;
}

[BJOI2019]奥术神杖

原文:https://www.cnblogs.com/ZH-comld/p/10781597.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!