企业单页网站模板,在电脑上做苗木网站,服务器做网站FTP必要性大吗,龙岩网红隧道在哪正题
题目链接:https://www.luogu.com.cn/problem/P5319 题目大意
一个长度为nnn的串TTT#xff0c;用0∼90\sim 90∼9填充所有的...。
然后给出mmm个串和它们的价值。
一个填充方案的价值等于#xff1a;若TTT中出现了ccc个给出的串#xff0c;那价值等于它们的价值乘积…正题
题目链接:https://www.luogu.com.cn/problem/P5319 题目大意
一个长度为nnn的串TTT用0∼90\sim 90∼9填充所有的...。
然后给出mmm个串和它们的价值。
一个填充方案的价值等于若TTT中出现了ccc个给出的串那价值等于它们的价值乘积开ccc次根。
1≤m≤1501,1≤Vi≤1091\leq m\leq 1501,1\leq V_i\leq 10^91≤m≤1501,1≤Vi≤109 解题思路
ans∏Vicans\sqrt[c]{\prod V_i}ansc∏Vi lnans1c∑(lnVi)\ln ans\frac{1}{c}\sum (\ln V_i)lnansc1∑(lnVi) 然后就是一个0/10/10/1分数规划问题了因为要匹配所以要先跑一个ACACAC自动机上dpdpdp就好了。
时间复杂度O(n2log109)O(n^2\log 10^9)O(n2log109) code
#includecstdio
#includecstring
#includealgorithm
#includecmath
#includequeue
using namespace std;
const int N1510;
const double eps1e-6;
int n,m,cnt,ch[N][10],fail[N],num[N];
double w[N],v[N],f[N][N];
pairint,intpre[N][N];queueint q;
char T[N],S[N];
void Insert(char *s,double val){int lstrlen(s),x0;for(int i0;il;i){int cs[i]-0;if(!ch[x][c])ch[x][c]cnt;xch[x][c];}v[x]val;num[x];return;
}
void Build(){for(int i0;i10;i)if(ch[0][i])q.push(ch[0][i]);while(!q.empty()){int xq.front();q.pop();v[x]v[fail[x]];num[x]num[fail[x]];for(int i0;i10;i){if(!ch[x][i])ch[x][i]ch[fail[x]][i];else{fail[ch[x][i]]ch[fail[x]][i];q.push(ch[x][i]);}}}return;
}
int check(double mid){for(int i0;icnt;i)w[i]v[i]-mid*num[i];for(int i0;in;i)for(int j0;jcnt;j)f[i][j]-1e100;f[0][0]0;for(int i1;in;i){for(int j0;jcnt;j){if(f[i-1][j]-1e99)continue;if(T[i].){for(int k0;k10;k){int ych[j][k];if(f[i][y]f[i-1][j]w[y])f[i][y]f[i-1][j]w[y],pre[i][y].firstj,pre[i][y].secondk;}}else{int kT[i]-0,ych[j][k];if(f[i][y]f[i-1][j]w[y])f[i][y]f[i-1][j]w[y],pre[i][y].firstj,pre[i][y].secondk;}}}int root0;for(int j0;jcnt;j)if(f[n][j]f[n][root])rootj;return root;
}
void print(int k,int x){if(k1)return; print(k-1,pre[k][x].first);printf(%d,pre[k][x].second);return;
}
int main()
{scanf(%d%d,n,m);scanf(%s,T1);for(int i1;im;i){int x;scanf(%s,S);scanf(%d,x);Insert(S,log(x));}Build();double l0,r21;while(r-leps){double mid(lr)/2.0;int rootcheck(mid);if(f[n][root]eps)lmid;else rmid;}int rootcheck(l);print(n,root);return 0;
}
