题解：AT_abc400_f [ABC400F] Happy Birthday! 3

wflhx2011 · 2025-04-07 15:32:53 · 题解

发现一段区间可以由两次修改小区间合并过来，考虑区间 dp。

设 f_{l,r} 表示使区间 [l,r] 为最后结果的最小代价。

首先因为在环上，不妨断环成链，即复制一次原序列接到最后，这样就解决了存在环无法转移的问题。

初始状态为 f_{i,i}=X_{C_i}+1，也就是只修改这一个位置。

然后，对于转移方程，考虑 r 这个位置可以如何得到。

• 只修改 r 这个位置，此时 f_{l,r}=f_{l,r-1}+f_{r,r}。

• 修改 [i,r] 这段区间，其中 l\le i< r。此时应满足 C_i=C_r，否则，i 这个点需要再次修改，此时把 i 和 r 放在两次修改中分别修改，一定不会使答案更劣。

  那么考虑先修改好区间 [l,i]，然后对于区间 [i+1,r] 在之前对 i 的修改中一起修改（或者理解为扩展对 i 的修改到 r），这里因为只修改了一次，所以不需要额外加 X_{C_i}。最后修改 [i+1,r-1]，也就是 f_{l,r}=f_{l,i}+r-i+f_{i+1,r-1}。

对于二者取最小值。

这里注意不能把初值赋为极大值，因为转移时可能出现 f_{l,r} 中 l>r，正确值应为 0，但不会被转移到，如果赋为极大值就无法从该状态转移出去。

代码：

#include<bits/stdc++.h>
using namespace std;
long long n,c[805],f[805][805],x[805],res=1e18; 
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>c[i],c[n+i]=c[i];
    for(int i=1;i<=n;i++)
        cin>>x[i];
//  memset(f,0x3f,sizeof(f)); 
    for(int i=1;i<=2*n;i++)
        f[i][i]=x[c[i]]+1;
    for(int len=2;len<=2*n;len++)
        for(int l=1;l+len-1<=2*n;l++)
        {
            int r=l+len-1;
            f[l][r]=f[l][r-1]+f[r][r];
            for(int i=l;i<r;i++)
                if(c[i]==c[r])
                    f[l][r]=min(f[l][r],f[l][i]+r-i+f[i+1][r-1]);
        }
    for(int l=1;l<=n+1;l++)
        res=min(res,f[l][l+n-1]);
    cout<<res;  
    return 0;
}