Loj #3089. 「BJOI2019」奥术神杖
题目描述
Bezorath 大陆抵抗地灾军团入侵的战争进入了僵持的阶段，世世代代生活在 Bezorath 这片大陆的精灵们开始寻找远古时代诸神遗留的神器，试图借助神器的神秘
力量帮助她们战胜地灾军团。
在付出了惨痛的代价后，精灵们从步步凶险的远古战场取回了一件保存尚完好的神杖。但在经历过那场所有史书都视为禁忌的“诸神黄昏之战”后，神杖上镶嵌的奥术宝石
已经残缺，神力也几乎消耗殆尽。精灵高层在至高会议中决定以举国之力收集残存至今的奥术宝石，并重金悬赏天下能工巧匠修复这件神杖。
你作为神术一脉第五百零一位传人，接受了这个艰巨而神圣的使命。 神杖上从左到右镶嵌了 (n) 颗奥术宝石，奥术宝石一共有 (10) 种，用数字 0123456789
表示。有些位置的宝石已经残缺，用 . 表示，你需要用完好的奥术宝石填补每一处残缺的部分（每种奥术宝石个数不限，且不能够更换未残缺的宝石）。古老的魔法
书上记载了 (m) 种咒语 ((S_i,V_i))，其中 (S_i) 是一个非空数字串，(V_i) 是这种组合能够激发的神力。
神杖的初始神力值 (mathrm{Magic} = 1)，每当神杖中出现了连续一段宝石与 (S_i) 相等时，神力值 (mathrm{Magic}) 就会乘以 (V_i)。但神杖如果包含
了太多咒语就不再纯净导致神力降低：设 (c) 为神杖包含的咒语个数（若咒语类别相同但出现位置不同视为多次），神杖最终的神力值为 (sqrt[c]{mathrm{Magic}})。（若 (c = 0) 则神杖最终神力值为 (1)。）
例如有两种咒语 ((01,3)) 、((10,4))，那么神杖 0101 的神力值为 (sqrt[3]{ 3 imes 4 imes 3})。
输入格式
第一行两个正整数 (n,m)，表示宝石数和咒语数。
第二行为一个长度为 (n) 的字符串 (T)，表示初始的神杖。
接下来 (m) 行每行一个非空数字串 (S_i) 和一个正整数 (V_i)，表示每种咒语。
输出格式
输出最终神杖上从左到右镶嵌的宝石，多解时任意输出一个即可。
数据范围与提示
(n,sum_{i=1}^m|S_i|leq 150)。(V_ileq 10^9)
(\)
首先将答案取一个对数，
要求最大化(frac{sum_{i=1}^c V_i}{c})就是裸的(0/1)分数规划问题（我竟然没看出来，真是越来越zz了）。具体实现时在(AC)自动机上(DP)就好了。
代码：
#include<bits/stdc++.h>
#define ll long long
#define N 1505
#define eps 1e-8
using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
int n,m;
char s[N],t[N];
struct trie {
int ch[10];
int cnt,fail;
double sum;
}tr[N];
int cnt=1;
void Insert(char *s,double val) {
int len=strlen(s+1);
int v=1;
for(int i=1;i<=len;i++) {
int j=s[i]-'0';
if(!tr[v].ch[j]) tr[v].ch[j]=++cnt;
v=tr[v].ch[j];
}
tr[v].cnt++;
tr[v].sum+=val;
}
void build_fail() {
static queue<int>q;
for(int i=0;i<10;i++) {
if(!tr[1].ch[i]) tr[1].ch[i]=1;
else {
tr[tr[1].ch[i]].fail=1;
q.push(tr[1].ch[i]);
}
}
while(!q.empty()) {
int v=q.front();
q.pop();
tr[v].cnt+=tr[tr[v].fail].cnt;
tr[v].sum+=tr[tr[v].fail].sum;
for(int i=0;i<10;i++) {
if(!tr[v].ch[i]) tr[v].ch[i]=tr[tr[v].fail].ch[i];
else {
int sn=tr[v].ch[i];
tr[sn].fail=tr[tr[v].fail].ch[i];
q.push(sn);
}
}
}
}
double f[N][N];
double tag[N];
struct node {
int x,y,type;
node() {}
node(int _x,int _y,int _type) {
x=_x,y=_y,type=_type;
}
};
node fr[N][N];
bool chk(double ans) {
for(int i=1;i<=cnt;i++) tag[i]=tr[i].sum-tr[i].cnt*ans;
for(int i=0;i<=n;i++)
for(int j=1;j<=cnt;j++)
f[i][j]=-1e9;
f[0][1]=0;
for(int i=0;i<n;i++) {
for(int j=1;j<=cnt;j++) {
if(f[i][j]<-1e6) continue ;
if(s[i+1]=='.') {
for(int k=0;k<10;k++) {
int q=tr[j].ch[k];
if(f[i][j]+tag[q]>f[i+1][q]) {
f[i+1][q]=f[i][j]+tag[q];
fr[i+1][q]=node(i,j,k);
}
}
} else {
int q=tr[j].ch[s[i+1]-'0'];
if(f[i][j]+tag[q]>f[i+1][q]) {
f[i+1][q]=f[i][j]+tag[q];
fr[i+1][q]=node(i,j,s[i+1]-'0');
}
}
}
}
for(int i=1;i<=cnt;i++) if(f[n][i]>0) return 1;
return 0;
}
void out(int x,int y) {
if(!x) return ;
out(fr[x][y].x,fr[x][y].y);
cout<<fr[x][y].type;
}
int main() {
n=Get(),m=Get();
scanf("%s",s+1);
for(int i=1;i<=m;i++) {
scanf("%s",t+1);
double v=Get();
Insert(t,log2(v));
}
build_fail();
double l=0,r=100,mid;
while(l+eps<r) {
mid=(l+r)/2.0;
if(chk(mid)) l=mid;
else r=mid-eps;
}
chk(l);
for(int i=1;i<=cnt;i++) {
if(f[n][i]>0) {
out(n,i);
break ;
}
}
return 0;
}