【学习笔记】「JOISC 2022 Day2」复制粘贴 3

看了正解。我觉得很厉害。虽然用减枝水过去了。

区间$dp$。但是这个转移怎么看都不是$O(1)$的。

$\text{border}$ 那么$\text{trick}$应该都能看出来。能进行剪切操作当且仅当$s_{[l,p]}=s_{[q,r]}$，显然直接跳$\text{fail}$链即可。厉害的地方来了，对于两个相同的子串只用计算一次，而每跳一次至少会出现一对相同的子串，因此总转移数目只有$O(n^2)$。

问题在于求出区间$[l,r]$内最多能选多少个不重复的$s_{[l,p]}$。更厉害的地方来了，这个东西可以倍增预处理，设$g_{l,r,k}$表示和$s_{[l,r]}$相同的不重叠的第$2^k$个串的左端点，然后就做完了。

复杂度是严格的$O(n^2\log n)$。 当然减一减枝也能过。

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
int n,nxt[2505][2505],to[2505][2505];
int trie[2505*2505][26],g[2505][2505][12],len[2505*2505],tot;
ll dp[2505][2505],A,B,C;
vector<int>pos[2505*2505];
string s;
void chmin(ll &x,ll y){x=min(x,y);}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>s;memset(dp,0x3f,sizeof dp);cin>>A>>B>>C;//fixedfor(int i=0;i<n;i++){nxt[i][i]=i-1;for(int j=i+1;j<n;j++){int k=nxt[i][j-1];while(k>=i&&s[k+1]!=s[j])k=nxt[i][k];if(s[k+1]==s[j])k++;nxt[i][j]=k;}}for(int i=0;i<n;i++){int it=0;for(int j=i;j<n;j++){if(!trie[it][s[j]-'a'])trie[it][s[j]-'a']=++tot,len[tot]=j-i+1;it=trie[it][s[j]-'a'];pos[it].pb(i);to[i][j]=it;}}for(int i=1;i<=tot;i++){sort(pos[i].begin(),pos[i].end());int k=0;for(int j=0;j<pos[i].size();j++){while(k<pos[i].size()&&pos[i][k]-pos[i][j]<len[i])k++;if(k!=pos[i].size()){g[pos[i][j]][len[i]][0]=pos[i][k];}}}for(int k=1;k<=11;k++){for(int i=0;i<n;i++){for(int j=1;j<=n-i;j++){if(g[i][j][k-1])g[i][j][k]=g[g[i][j][k-1]][j][k-1];}}}for(int i=0;i<n;i++)dp[i][i]=A;for(int len=2;len<=n;len++){for(int i=0;i<n-len+1;i++){int j=i+len-1;if(pos[to[i][j]][0]!=i){dp[i][j]=dp[pos[to[i][j]][0]][pos[to[i][j]][0]+len-1];continue;}chmin(dp[i][j],dp[i+1][j]+A);chmin(dp[i][j],dp[i][j-1]+A);//fixedfor(int k=nxt[i][j];k>=i;k=nxt[i][k]){int tot=1,nowl=i,len2=k-i+1;for(int l=11;l>=0;l--){if(g[nowl][len2][l]&&g[nowl][len2][l]<=j-len2+1){tot+=1<<l;nowl=g[nowl][len2][l];}}chmin(dp[i][j],dp[i][k]+B+tot*C+(len-tot*len2)*A);}}}cout<<dp[0][n-1];
}