颜色扩散类dp及其优化：0919T2

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133047170

http://cplusoj.com/d/senior/p/330

此题前半部分是AGC058B

这是一个颜色扩散类dp，对于这类dp，存在一个性质。

假如一个区间被 $i$ 染，一个被 $j$ 染，则必然满足 $i<j$ （这是下标）

所以转移可以用前缀和优化至 $O(n^2)$

for(i=1; i<=n; ++i) {
		for(j=1, mx=0; j<=n; ++j) {
			mx=max(mx, f[i-1][j]); 
			f[i][j]=mx+(a[j]==b[i] && i>=l[j] && i<=r[j]); 
		}
	}
	for(i=1; i<=n; ++i) ans=max(f[n][i], ans); 

---

然后针对题目的特殊限定，我们可以发现， $a_j=b_i$ 成立只有 $n$ 个，所以就变成了线段树优化问题。

for(i=1; i<=n; ++i) mp[a[i]]=i; 
for(i=1; i<=n; ++i) {
	if(!mp[b[i]]) continue; 
	j=mp[b[i]];  
	if(!(i>=l[j] && i<=r[j])) continue; 
	k=Seg.add(1, 1, n, j); 
	if(j!=n) Seg.que(1, 1, n, j+1, n, k); 
}
printf("%lld", Seg.mx[1]);