P9523

· · 题解

先 orz oyds。但是为什么没有 oyds 的简单预处理做法啊。

区间 dp。dp_{i,j} 表示凑出区间 [i,j] 的最小代价。考虑枚举当前区间 [i,j] 与 k，找到一个最大的 p，使得 [i,j] 在区间 [p,j] 中不重叠地出现了 k 次。则有转移：

dp_{p,j}\leftarrow\min(dp_{p,j},dp_{i,j}+B+k\times C+(j-p+1-k\times len)\times A)

以及最基本的：

dp_{i,j}\leftarrow\min(dp_{i+1,j}+A,dp_{i,j-1}+A,dp_{i,j})

这部分复杂度为 O(\sum\frac{n}{j-i+1})=O(n^2\ln n)。

现在就要考虑怎么找这个 k 对应的 p。考虑 dp 求出 S 每两个后缀的 \operatorname{lcp}，然后处理出对于一对 (i,k) 的最大的 j<i，使得 \operatorname{lcp}(S[i:n],S[j:n])\ge k。这个东西可以先记录 =k 的情况，然后求后缀最大值。注意此处由于两个串不能重叠，所以预处理时令 \operatorname{lcp}(S[i:n],S[j:n])\le i-j。

这部分 O(n^2)。

简单好写。

code：

int n,m,lcp[N][N],pre[N][N];
ll A,B,C,dp[N][N];
char s[N];
void Yorushika(){
    scanf("%d%s%lld%lld%lld",&n,s+1,&A,&B,&C);
    drep(i,n,1){
        drep(j,i-1,1){
            lcp[i][j]=s[i]==s[j]?lcp[i+1][j+1]+1:0;
            lcp[i][j]=min(lcp[i][j],i-j);
            if(!pre[i][lcp[i][j]])
                pre[i][lcp[i][j]]=j;
        }
        drep(j,n,1){
            pre[i][j]=max(pre[i][j],pre[i][j+1]);
        }
    }
    mems(dp,0x3f);
    rep(i,1,n){dp[i][i]=A;}
    rep(len,1,n){
        rep(i,1,n-len+1){
            int j=i+len-1;
            dp[i][j]=min({dp[i][j],dp[i+1][j]+A,dp[i][j-1]+A});
            int p=i;
            rep(k,1,j/len){
                p=pre[p][len];
                if(!p)break;
                dp[p][j]=min(dp[p][j],dp[i][j]+B+(k+1)*C+(j-p+1-(k+1)*len)*A);
            }
        }
    }
    printf("%lld\n",dp[1][n]);
}
signed main(){
    int t=1;
    //  scanf("%d",&t);
    while(t--)
        Yorushika();
}

upd 11.27：修改了若干错误。