DP 做题记录 II.

里面会有一些数据结构优化 DP 的题目（如 XI.），以及普通 DP。

*I. P3643 [APIO2016]划艇

题意简述：给出序列 \(a_i,b_i\)，求出有多少序列 \(c_i\) 满足 \(c_i=-1\) 或 \(c_i\in[a_i,b_i]\)，同时非 \(-1\) 的部分单调递增。

直到做到这题我才意识到我的 DP 水平有多菜。

注意到值域过大，于是对区间进行离散化，设离散化后的端点分别为 \(p_1,p_2,\cdots,p_c\)。注意要将 \([a_i,b_i]\) 变成 \([a_i,b_i+1)\)，即将 \(b_i\) 加 \(1\)，方便计算答案。

接下来考虑 DP：设 \(f_{i,j}\) 表示第 \(i\) 个学校派出划艇数量在 \(L_j=[p_j,p_{j+1})\) 之间时的方案数。

错误思路：\(f_{i,j}=\begin{cases}\sum_{pos=1}^{i-1}\sum_{k=1}^{j-1}f_{pos,k}\times (p_{j+1}-p_j)&[p_j,p_{j+1})\subseteq[a_i,b_i)\\0&\mathrm{otherwise}\end{cases}\)。错误原因：I. 没有考虑边界条件 & 枚举下界。II. 没有考虑在同一区间内也合法的情况。

边界条件就是 \(f_{i,0}=1\)，并且注意 \(pos,k\) 的枚举下界应为 \(0\)。

考虑在同一区间内合法的情况：不妨枚举最右端的不在区间 \(j\) 的位置 \(pos\)，那么剩下来 \(i-pos\) 个位置。假设当中有 \(m\) 个位置满足可以落在区间 \(j\) 上，那么方案数就相当于从 \(m-1\) 个 \(-1\) 和 \(L_j\) 个数 \(p_j,p_j+1,\cdots,p_{j+1}-1\) 中选出 \(m\) 个数（因为位置 \(i\) 必须选所以是 \(m-1\) 而不是 \(m\)；\(-1\) 相当于不选），即 \(\binom{m+L_j-1}{m}\)。

综上所述，更新后的转移方程应为 \(f_{i,j}=\begin{cases}\sum_{pos=0}^{i-1}\sum_{k=0}^{j-1}f_{pos,k}\times\binom{m+L_j-1}{m}&[p_j,p_{j+1})\subseteq[a_i,b_i)\\0&\mathrm{otherwise}\end{cases}\)。注意到后面的组合数可以 \(\mathcal{O}(1)\) 递推（\(\binom{m+L_j}{m+1}=\binom{m+L_j-1}{m}\times\frac{m+L_j}{m+1}\)），那么使用前缀和优化（因为 \(m\) 与枚举的 \(k\) 无关，所以记 \(s_{i,j}=\sum_{k=0}^j f_{i,k}\)，则上面那一坨可以写成 \(\sum_{pos=0}^{i-1}s_{pos,j-1}\times\binom{m+L_j-1}{m}\)）+ 倒序枚举 \(pos\)（实时更新 \(m\) 与组合数）即可 \(\mathcal{O}(n^3)\) 计算。

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N=500+5;

const int mod=1e9+7;

ll n,cnt,a[N],b[N],p[N<<1];

ll g[N],iv[N];

int main(){

	cin>>n,g[0]=1;

	for(int i=1;i<=n;i++){

		cin>>a[i]>>b[i],iv[i]=(i==1?1:-mod/i*iv[mod%i]%mod+mod);

		p[++cnt]=a[i],p[++cnt]=b[i]+1;

	} sort(p+1,p+cnt+1),cnt=unique(p+1,p+cnt+1)-p-1;

	for(int i=1;i<=n;i++){

		a[i]=lower_bound(p+1,p+cnt+1,a[i])-p;

		b[i]=lower_bound(p+1,p+cnt+1,b[i]+1)-p;

	} for(int i=1;i<cnt;i++){

		ll len=p[i+1]-p[i];

		for(int j=n;j;j--)

			if(a[j]<=i&&i<b[j]){

				ll f=0,m=0,C=1;

				for(int k=j;k;k--){

					if(a[k]<=i&&i<b[k])C=C*(m+len)%mod*iv[m+1]%mod,m++;

					f=(f+g[k-1]*C)%mod;

				} g[j]=(g[j]+f)%mod;

			}

	} ll ans=0;

	for(int i=1;i<=n;i++)ans=(ans+g[i])%mod;

	cout<<ans<<endl;

	return 0;

}

II. P7091 数上的树

题目传送门。

首先将 \(n\) 分解质因数，用 DFS 求出 \(n\) 的所有因数，记为 \(d_1,d_2,\cdots,d_c\)，跑一遍反素数那题的代码可知 \(c\leq 23327\)（

设 \(f_i\) 表示根节点为 \(d_i\) 时最小值。

显然，局部最优值可以保证整体最优值，且转移无后效性，即求 \(f_i\) 时不会影响 \(f_j\ (d_j<d_i)\)，故答案可以用树形 DP 求出，将所有因数排序后可以转化为序列上的 DP。

对于不能出现在树上的 \(d_i\) 直接 skip 即可。

设 \(g_i\) 表示 \(d_i\) 所含有的质因子个数。For example，\(12=2\times 2\times 3\)，所以 \(12\) 有 \(3\) 个质因子。在本题中，\(g_{i}\) 也表示以 \(d_i\) 为根的子树的节点个数，不难发现其为定值。

假设当前转移 \(f_i\) 决策点为 \(j,k\ (d_j\times d_k=d_i)\)，那么对于 \(d_j\) 和 \(d_k\) 子树内两两组合出的 pairs 的贡献可以直接由 \(f_j+f_k\) 推得，剩下来只有两种情况：

Case 1：\(d_j\) 和 \(d_k\) 子树内各一个节点组合出的 pairs。因为它们的 LCA 是 \(d_i\)，且共有 \(g_j\times g_k\) 对 pairs，故贡献为 \(g_j\times g_k\times d_i\)。
Case 2：\(d_i\) 和任意一个节点组合出的 pairs。显然贡献为 \(g_i\times d_i\)。

转移方程：

\[f_i=\min_{d_j\times d_k=d_i}f_j+f_k+(g_j\times g_k+g_i)\times d_i
\]

，其中 \(g_i=g_j+g_k+1\) 可以在 DP 时一并求出。

这样子搞是 \(\mathcal O(c^3)\) 的，显然无法接受。

剪枝 1：在枚举内层循环 \(j\) 时发现 \(k\) 有单调性，所以直接用 pointer 代替 \(k\) 即可。这样时间复杂度降为了 \(\mathcal O(c^2)\)。
剪枝 2：当 \(j>k\) 时直接 break，减小常数。

综上，我们有了一个 \({\mathcal O}(\sqrt n+m\log c+c^2)\) 的算法（分解质因数 + 处理限制需要二分查找 + DP），代码如下：

ll n,m,num[N],f[N];

ll cnt,pr[N],c[N],tot;

ll fc[N],il[N],d;

map <ll,int> isp;

void dfs(int pos,ll prod){

	if(pos>cnt){

		if(prod>1)fc[++d]=prod;

		return;

	} for(int i=0;i<=c[pos];i++)dfs(pos+1,prod),prod*=pr[pos];

}

int main(){

	cin>>n>>m;

	// factor

	ll tmp=n;

	for(ll i=2;i*i<=n;i++)

		if(n%i==0){

			pr[++cnt]=i,isp[i]=1;

			while(n%i==0)c[cnt]++,tot++,n/=i;

		}

	if(n>1)pr[++cnt]=n,tot++,c[cnt]=1,isp[n]=1;

	n=tmp;

	// find factors

	dfs(1,1);

	sort(fc+1,fc+d+1);

	// limit

	for(int i=1;i<=m;i++){

		ll val=read();

		int pos=lower_bound(fc+1,fc+d+1,val)-fc;

		if(pos<=d&&fc[pos]==val)il[pos]=1; // 表示 pos 不能出现

	}

	// dp

	for(int i=1;i<=d;i++){

		if(il[i])continue;

		if(isp[fc[i]]){

			num[i]=1,f[i]=fc[i];

			continue;

		} il[i]=1,f[i]=inf; // 如果无法由以前的 j,k 转移得到那么 i 也无法得到

		int p=i-1;

		for(int j=1;j<i;j++){

			if(fc[i]%fc[j])continue;

			while(fc[p]>fc[i]/fc[j])p--;

			if(j>p)break;

			if(!il[j]&&!il[p])f[i]=min(f[i],f[j]+f[p]+num[j]*num[p]*fc[i]+(num[i]=num[j]+num[p]+1)*fc[i]),il[i]=0;

		}

	} if(il[d])puts("-1");

	else cout<<(ll)f[d]<<endl;

	return 0;

}

III. CF1156F Card Bag

题目传送门。

题意简述：有 \(n\) 张卡牌，每张卡牌有数字 \(a_1,a_2,\cdots,a_n\)。现在随机抽取卡牌，不放回，设本次抽到的卡牌为 \(x\)，上次抽到的卡牌为 \(y\)，若 \(x=y\) 则游戏胜利；若 \(x<y\) 则输掉游戏；若 \(x>y\) 则游戏继续。求获胜概率。

\(a_i\leq n\leq 5\times 10^3\)。

下文认为 \(a_i\) 与 \(n\) 同阶。

不难发现我们只关心卡牌上的数字，所以开个桶维护每个数出现了几次。又因为只能从小往大抽，即无后效性，所以考虑 DP。

设 \(f_{i,j}\) 为 共抽了 \(j\) 次，每个数最多抽到一次，最后一次抽到数字 \(i\) 的概率。

首先考虑如何转移：我们设数字 \(i\) 共有 \(sz_i\) 个，那么不难列出转移方程

\[f_{i,j}=\sum_{k=0}^{i-1}f_{k,j-1}\times \frac{sz_i}{n-j+1}
\]

，表示 在 \([1,i-1]\) 中抽了 \(j-1\) 个数 的概率乘上 抽到数字 \(i\) 的概率。这样转移的时间复杂度为 \(\mathcal{O}(n^3)\)，无法接受。

如果设 \(s_{i,j}\) 为 在 \(i\) 中抽了 \(j\) 个数 的概率，则有

\[s_{i,j}=\sum_{k=1}^{i}f_{i,j}
\]

，则转移方程可变形为

\[f_{i,j}=\frac{s_{i-1,j-1}sz_i}{n-j+1}
\]

。预处理逆元做到时间复杂度 \(\mathcal{O}(n^2)\)，可以接受。

这实际上就是具有实际意义的前缀和优化。

最后使用滚动数组可以将空间优化到 \(\mathcal{O}(n)\)。

需要注意初始值 \(f_{0,0}=1\)。

const int N=5e3+5;

ll n,ans,sz[N],f[2][N],s[2][N];

int main(){

	init(),cin>>n,s[0][0]=s[1][0]=1;

	for(int i=1,a;i<=n;i++)cin>>a,sz[a]++;

	for(int i=1,p=1;i<=n;i++,p^=1){

		for(int j=1;j<=i;j++){

			f[p][j]=s[p^1][j-1]*sz[i]%mod*iv[n-j+1]%mod;

			ans=(ans+s[p^1][j-1]*sz[i]*(sz[i]-1)%mod*iv[n-j+1]%mod*iv[n-j])%mod;

			s[p][j]=(s[p^1][j]+f[p][j])%mod;

		}

	} cout<<ans<<endl;

	return 0;

}

*IV. CF1542E2 Abnormal Permutation Pairs (hard version)

题解。

*V. AT693 文字列

很 nb 的题目，没想出来。

注意我们不关注字符的相对顺序，只关心有没有相邻的相同字符，因此考虑 DP：设 \(f_{i,j}\) 表示前 \(i\) 个字母构成的有 \(j\) 对相邻字符的字符串个数。转移时枚举 \(j\)，当前字母分几段，以及一共插入到几对相邻字符中，然后组合数算算即可。答案即为 \(f_{n,0}\)。

时间复杂度 \(\alpha n^3\)，其中 \(\alpha\) 是字符集大小，\(n\) 是字符总数。

可是我连第一步 DP 都没想出来。

#pragma GCC optimize(3)

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define pb push_back

#define mem(x,v) memset(x,v,sizeof(x))

#define mcpy(x,y) memcpy(x,y,sizeof(y))

const ll mod=1e9+7;

const int N=260+5;

ll c,sum,a[N],f[N][N],C[N][N];

int main(){

	for(int i=0;i<N;i++)

		for(int j=0;j<=i;j++)

			C[i][j]=(j==0||j==i?1:C[i-1][j-1]+C[i-1][j])%mod;

	for(int i=0;i<26;i++)cin>>a[i];

	f[0][max(0ll,a[0]-1)]=1,sum=a[0];

	for(int i=1;i<26;i++){

		if(!a[i])continue;

		c++;

		for(int j=0;j<=sum;j++)

			for(int k=0;k<=a[i];k++)

				for(int l=0;l<=k;l++)

					if(l<=j){

						int nw=j-l+(a[i]-k);

						f[c][nw]=(f[c][nw]+f[c-1][j]*C[a[i]-1][k-1]%mod*C[j][l]%mod*C[sum+1-j][k-l])%mod;

					}

		sum+=a[i];

	}

	cout<<f[c][0]<<endl;

	return 0;

}

*VI. AT3859 [AGC020E] Encoding Subsets

好题。首先考虑没有子集限制怎么做：单纯设一个状态好像不好转移，因此设 \(f_{l,r}\)​ 为不需要括号括起来的方案数，\(g_{l,r}\)​ 为只能用括号括起来或只有单字符的方案数，那么枚举第一个括号的结尾位置，有 \(f_{l,r}=\sum_{k=l}^r g_{l,k}f_{k+1,r}\)​，\(g_{l,r}=\sum_{d|r-l+1\ \land\ d<r-l+1}g(l,l+d-1)[s_{l,l+d-1}=\cdots=s_{r-d+1,r}]\)，注意观察边界条件​。

有一部分我理解了很久才明白：在计算 \(f_{l,r}\)​ 的过程中，如果第一个括号的开头不在 \(l\)​ 的位置，那么会计入 \(g_{l,l}f_{l+1,r}\)​ 的贡献。

但是这么做对于本题就不行了，不过我们受到上述启发，可以用字符串作为 DP 的变量。注意到字符串压缩时，只要有一个字符串的某一位为 \(0\)​​，那么最终得到的字符串的该位也只能为 \(0\)​​，比如说 \(01/11/10\)​ 只能压缩成 \(00\)​，而 \(011/110\)​ 的压缩结果就是 \(010\)​，i.e. 第二位既可以是 \(0\)​ 也可以是 \(1\)​​。然后就可以 DP 了，时间复杂度 \(\mathcal{O}(\rm{can\ pass})\)​。

const int N=5e3+5;

const ll mod=998244353;

map <string,int> f,g;

int calcg(string s);

int calcf(string s){

	if(s.size()==0)return 1;

	if(s.size()==1)return s[0]-'0'+1;

	if(f.find(s)!=f.end())return f[s];

	int res=0;

	for(int i=1;i<=s.size();i++){

		string pre="",suf="";

		for(int j=0;j<i;j++)pre+=s[j];

		for(int j=i;j<s.size();j++)suf+=s[j];

		res=(res+1ll*calcg(pre)*calcf(suf))%mod;

	} return f[s]=res;

}

int calcg(string s){

	if(s.size()==0)return 1;

	if(s.size()==1)return s[0]-'0'+1;

	if(g.find(s)!=g.end())return g[s];

	int res=0;

	for(int i=1;i<s.size();i++)

		if(s.size()%i==0){

			string nw="";

			for(int j=0;j<i;j++)nw+="1";

			for(int j=0;j<s.size();j++)nw[j%i]=((nw[j%i]-'0')&(s[j]-'0'))+'0';

			res=(res+calcf(nw))%mod;

		} return g[s]=res;

}

int main(){

	string s; cin>>s,cout<<calcf(s)<<endl;

	return 0;

}

*VII. P2470 [SCOI2007]压缩

双倍经验，不过略有区别：设 \(f_{i,j}\)​ 表示中间没有 M 的方案数（假定 \(i\)​ 前面的所有字符不在缓冲串中），\(g_{i,j}\)​ 表示中间有 M 的方案数，那么有 \(f_{l,r}=\min_{k=l}^{r-1}(f_{i,k}+r-k)\)（为什么是 \(f_{i,k}\)：因为我们假定进入 \([l,r]\) 时缓冲串为空，所以一定是前缀，如果是 \(f_{k,r}\) 那 \(l\sim k-1\) 的字符就在缓冲串里面了），不要忘记用 \(r-l+1\) 以及 \(f_{l,mid}+1\)（如果 \(r-l+1\) 是偶数且 \(s_{l\sim mid}=s_{mid+1\sim r}\)）更新 \(f_{l,r}\)。\(g\) 就很简单了啊，枚举 M 出现的位置，那么，\(\min_{k=l}^{r-1}(\min(f_{i,k},g_{i,k})+\min(f_{k+1,r},g_{k+1,r})+1)\)​。​时间复杂度 \(\mathcal{O}(n^3)\)。

const int N=50+5;

const ll mod=998244353;

char s[N];

int f[N][N][2];

bool vf[N][N][2];

bool check(int l,int r){

	if(r-l+1&1)return 0;

	for(int i=l,j=l+r+1>>1;j<=r;i++,j++)

		if(s[i]!=s[j])return 0;

	return 1;

}

int cmin(int &x,int y){if(x>y)x=y;}

int F(int l,int r,int tp){

	if(l>r)return 0;

	if(l==r)return 1;

	if(vf[l][r][tp])return f[l][r][tp];

	vf[l][r][tp]=1,f[l][r][tp]=r-l+1;

	if(tp==0){

		if(check(l,r))cmin(f[l][r][0],F(l,l+r>>1,0)+1);

		for(int i=l;i<r;i++)cmin(f[l][r][0],F(l,i,0)+r-i);

	} else for(int i=l;i<r;i++)

		cmin(f[l][r][1],min(F(l,i,0),F(l,i,1))+min(F(i+1,r,0),F(i+1,r,1))+1);

	return f[l][r][tp];

}

int main(){

	scanf("%s",s+1);

	cout<<min(F(1,strlen(s+1),0),F(1,strlen(s+1),1))<<endl;

	return 0;

}

VIII. P4302 [SCOI2003]字符串折叠

三倍经验。和 AT3859 一模一样了属于是。

const int N=100+5;

const ll mod=998244353;

char s[N];

int f[N][N][2];

bool vf[N][N][2];

int cmin(int &x,int y){if(x>y)x=y;}

int F(int l,int r,int tp){

	if(l>=r)return r-l+1;

	if(vf[l][r][tp])return f[l][r][tp];

	vf[l][r][tp]=1,f[l][r][tp]=r-l+1;

	if(tp==0)for(int i=l;i<=r;i++)cmin(f[l][r][0],F(l,i,1)+F(i+1,r,0));

	else for(int i=1;i<r-l+1;i++)if((r-l+1)%i==0){

		bool ok=1; for(int j=l+i;j<=r;j++)ok&=s[j]==s[j-i];

		if(ok)cmin(f[l][r][1],F(l,l+i-1,0)+3+((r-l+1)/i>=10));

	} return f[l][r][tp];

}

int main(){

	scanf("%s",s+1),cout<<F(1,strlen(s+1),0)<<endl;

	return 0;

}

*IX. CF67C Sequence of Balls

若没有 4 操作，有一个显然的 DP，不谈。

考虑 swap 操作究竟应该怎么用：设 \(B_j\) 在 \(A_{1\sim i-1}\) 的最后一次出现在位置 \(x\)，\(A_i\) 在 \(B_{1\sim j-1}\) 的最后一次出现在位置 \(y\)​。​如果 \(x,y\) 至少有一个不存在，那么显然 swap 不优。否则我们删掉 \(A_{x+1\sim i-1}\)，swap，再在中间插入 \(B_{y+1\sim j-1}\) 即可。

正确性其实挺难说明的，结合 \(2t_e\geq t_i+t_d\) 感性理解一下，时间复杂度 \(\mathcal{O}(n^2)\)。

const int N=5e3+5;

int f[N][N],pres[N],pret[N];

int ti,td,tr,te;

string s,t;

int main(){

	cin>>ti>>td>>tr>>te>>s>>t; memset(f,0x3f,sizeof(f));

	for(int i=0;i<=s.size();i++,mem(pret,0,N)){

		if(i>1)pres[s[i-2]]=i-1;

		for(int j=0;j<=t.size();j++){

			if(i==0){f[i][j]=j*ti; continue;}

			if(j==0){f[i][j]=i*td; continue;}

			f[i][j]=min(f[i-1][j]+td,f[i][j-1]+ti);

			if(s[i-1]==t[j-1])f[i][j]=min(f[i][j],f[i-1][j-1]);

			else f[i][j]=min(f[i][j],f[i-1][j-1]+tr);

			int x=pres[t[j-1]],y=pret[s[i-1]];

			if(x&&y)f[i][j]=min(f[i][j],f[x-1][y-1]+td*(i-x-1)+ti*(j-y-1)+te);

			pret[t[j-1]]=j;

		}

	}

	cout<<f[s.size()][t.size()]<<endl;

	return 0;

}

X. NOIP2021 六校联考 0820 T3 /se

题意简述：将 \(n\) 条线段划分为不超过 \(k\) 个集合，求每个集合中所有线段的并的长度之和的最大值。

\(k\leq n\leq 5000\)，\(l\leq r\leq 10^6\)。时限 1s，空限 512MB。

首先，对于完全覆盖某一条线段 \(i\) 的线段 \(j\) 来说，其实我们不需要考虑它：它要么和 \(i\) 分到一组，不会造成影响，要么单独被分到一组。

因此，找到所有不完全覆盖任何其它线段的所有线段，按右端点排序，显然左端点也是单调的，所以设计 DP \(f_{i,j}\) 表示前 \(i\) 条前段划分成了 \(j\) 个集合的答案。最后 \(f_{n,j}\) 和完全覆盖的线段合并贡献即可。时间复杂度 \(\mathcal{O}(nk)\)。

Trick：实际上，对于很多线段 DP 题目，我们可以挖掘性质使得所有需要考虑的线段在右端点单调的情况下，左端点也单调。

const int N=5e3+5;

int n,k,c,d;

ll ans,t[N],tt[N],pre[N],f[N][N];

struct seg{

	ll l,r;

	bool operator < (const seg &v) const{

		return r<v.r;

	}

	bool operator == (const seg &v) const{

		return l==v.l&&r==v.r;

	}

}tmp[N],s[N];

int main(){

	freopen("se.in","r",stdin);

	freopen("se.out","w",stdout);

	cin>>n>>k;

	for(int i=1;i<=n;i++)cin>>tmp[i].l>>tmp[i].r;

	for(int i=1;i<=n;i++){

		tt[i]=tmp[i].r-tmp[i].l;

		bool lap=0;

		for(int j=1;j<=n;j++)

			if(tmp[i].l<=tmp[j].l&&tmp[j].r<=tmp[i].r)

				if(tmp[i]==tmp[j]&&i<j||!(tmp[i]==tmp[j])){

					lap=1; break;

				}

		if(lap)t[++d]=tmp[i].r-tmp[i].l;

		else s[++c]=tmp[i];

	}

	sort(s+1,s+c+1),mem(f,N,0xcf);

	f[0][0]=f[c][0]=0;

	for(int i=1;i<=c;i++)

		for(int j=1;j<=min(k,i);j++){

			pre[j]=max(pre[j],f[i-1][j-1]+s[i].r);

			f[i][j]=max(0ll,pre[j]-s[i].l);

		}

	sort(t+1,t+d+1),reverse(t+1,t+d+1);

	sort(tt+1,tt+n+1),reverse(tt+1,tt+n+1);

	for(int j=1;j<=min(k,c);j++){

		ll sum=f[c][j];

		for(int i=1;i<=d&&i+j<=k;i++)sum+=t[i];

		ans=max(ans,sum);

	}

	ll sum=0;

	for(int i=1;i<=k-1;i++)sum+=tt[i];

	cout<<max(ans,sum)<<endl;

	return 0;

}

XI. NOIP2021 六校联考 0818 T2 看烟花

题意简述：给出 \(n\) 个字符串 \(S_i\)，求用这些字符串的所有子串拼出 \(T\) 的最小代价，与方案数 \(\bmod 998244353\)。使用一次 \(S_i\) 的子串代价为 \(C_i\)，方案不同当且仅当 \(T\) 中存在至少一个字符满足来自不同的字符串。

\(|T|\leq 10^5\)，\(n\leq 200\)，\(C_i\leq 10^4\)，\(|S_i|\leq 3\times 10^4\)。**保证 \(C_i\) 随机生成****。时限 6s。空限 512MB。

设 \(f_i,g_i\) 分别表示拼出 \(T_{1\sim i}\) 的最小代价与方案数。枚举位置 \(i\) 与字符串 \(j\)，找到 \(S_j\) 子串和 \(T_{1\sim i}\) 的后缀最长匹配长度 \(l\)，从 \(f_{i-l\sim i-1}\) 转移即可，方案数同理。可以对于每个 \(S_j\) 建出 SAM，\(i\) 移动时 \(\mathcal{O}(1)\) 更新 \(S_j\) 与 \(T_{1\sim i}\) 的 \(l\)。注意转移是一段区间，所以用线段树维护区间最小代价以及最小代价方案数即可做到 \(|T|n\log |T|\)，不过被卡常了，开 O3 勉强 \(5950\rm ms\) 通过。

#pragma GCC optimize(3)

pii operator + (pii x,pii y){

	pii z; z.fi=x.fi<y.fi?x.fi:y.fi,z.se=0;

	if(x.fi==z.fi)z.se=x.se;

	if(y.fi==z.fi)z.se+=y.se;

	if(z.se>=mod)z.se-=mod;

	return z;

}

const int N=1e5+5;

const int S=6e4+5;

const pii inf={2e9,0};

struct SAM{

	char s[S];

	int l,cnt,las,cost,p,nwlen;

	int son[S][5],fa[S],len[S];

	void ins(char s){

		int it=s-'a',p=las,cur=++cnt;

		las=cur,len[cur]=len[p]+1;

		while(!son[p][it])son[p][it]=cur,p=fa[p];

		if(!p)return fa[cur]=1,void();

		int q=son[p][it];

		if(len[p]+1==len[q])return fa[cur]=q,void();

		int cl=++cnt;

		fa[cl]=fa[q],fa[q]=fa[cur]=cl;

		cpy(son[cl],son[q],5),len[cl]=len[p]+1;

		while(son[p][it]==q)son[p][it]=cl,p=fa[p];

	}

	void build(){

		cnt=las=1,scanf("%d%s",&cost,s+1),l=strlen(s+1);

		for(int i=1;i<=l;i++)ins(s[i]);

	}

	int jump(char s){

		int it=s-'a';

		while(p){

			if(!son[p][it])p=fa[p],nwlen=len[p];

			else return p=son[p][it],++nwlen;

		} return p=1,0;

	}

}tr[205];

char t[N];

int n,len;

pii val[N<<2],v;

int p,ql,qr;

void ins(int l=0,int r=len,int x=1){

	if(l==r)return val[x]=v,void();

	int m=l+r>>1;

	if(p<=m)ins(l,m,x<<1);

	else ins(m+1,r,x<<1|1);

	val[x]=val[x<<1]+val[x<<1|1];

}

pii quer(int l=0,int r=len,int x=1){

	if(ql>qr)return inf;

	if(ql<=l&&r<=qr)return val[x];

	int m=l+r>>1; pii ans=inf;

	if(ql<=m)ans=ans+quer(l,m,x<<1);

	if(m<qr)ans=ans+quer(m+1,r,x<<1|1);

	return ans;

}

void modify(int P,pii V){p=P,v=V,ins();}

pii query(int l,int r){ql=l,qr=r; return quer();}

int main(){

	freopen("firework.in","r",stdin);

	freopen("firework.out","w",stdout);

	scanf("%s%d",t+1,&n),len=strlen(t+1);

	for(int i=1;i<=n;i++)tr[i].build(),tr[i].p=1;

	modify(0,{0,1});

	for(int i=1;i<=len;i++){

		pii ans=inf;

		for(int j=1;j<=n;j++){

			int mxl=tr[j].jump(t[i]);

			pii res=query(i-mxl,i-1);

			res.fi+=tr[j].cost;

			ans=ans+res;

		}

		if(i<len)modify(i,ans);

		else cout<<ans.fi<<" "<<ans.se<<endl;

	}

    return 0;

}

区间查询，单点修改，且询问区间端点单调，可以用 BIT 优化。优化完变成 \(2500\rm ms\) 了。

pii c[N<<2];

void add(int x,pii y){x++; while(x)c[x]=c[x]+y,x-=x&-x;}

pii query(int x,int r){pii s=inf; x++,r++; while(x<=r)s=s+c[x],x+=x&-x; return s;}

官方解法中根据 \(C_i\) 随机生成，通过按 \(C_i\) 将 \(S_i\) 从小到大排序，然后若存在 \(j\) 满足\(C_j<C_i\) 且 \(l_j\geq l_i\)，那么 \(i\) 显然不优，可以舍去。这样就算使用线段树也可以通过了。

DP 做题记录 II.的相关教程结束。