题解：AT_abc400_f [ABC400F] Happy Birthday! 3

发现一段区间可以由两次修改小区间合并过来，考虑区间 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

，但不会被转移到，如果赋为极大值就无法从该状态转移出去。

代码：

CPP

#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;
}

题解：AT_abc400_f [ABC400F] Happy Birthday! 3

文章操作

相关推荐

评论

题解：AT_abc400_f [ABC400F] Happy Birthday! 3