题解 | #Floor Tiles#

##I

#include<bits/stdc++.h>
using namespace std;
int a[6005],p[3005];
int dp[6005], w[6005],l[6005],r[6005],len[6005];
bool cmp(int i, int j) {
	return len[i] < len[j];
}
int main()
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= 2 * n; i++) {
		cin >> a[i];
		if (l[a[i]] == 0) l[a[i]] = i;
		else r[a[i]] = i;
	}

	for (int i = 1; i <= n; i++) len[i] = r[i] - l[i] + 1;
	for (int i = 1; i <= n; i++) p[i] = i;
	sort(p + 1, p + 1 + n, cmp);//按照长度从小到大排序 区间dp

	for (int i = 1; i <= n; i++) {
		int x = p[i];
		for (int j = l[x] + 1; j < r[x]; j++) {//区间内dp从而计算出w[x]
			dp[j] = dp[j - 1] + x;//如果内部这一位没在小括号内的话 一位的贡献值位x 
			if (j == r[a[j]]&&l[a[j]]>l[x]) dp[j] = max(dp[j], dp[l[a[j]] - 1] + w[a[j]]);//在小括号内 计算贡献值
		}															//需要已知w[a[j]] 所以区间dp长度从小到到
		w[x] = x * 2 + dp[r[x] - 1];
		for (int j = l[x] + 1; j < r[x]; j++) dp[j] = 0;//清空 后面大括号还会包含这一段 要再dp
	}//把交叉包含的区间处理得到每个区间的最大的贡献值

	for (int i = 1; i <=2*n; i++) {//最后就是一个个交叉或隔开的小括号
		dp[i] = dp[i - 1];
		if (i == r[a[i]]) dp[i] = max(dp[i], dp[l[a[i]] - 1] + w[a[i]]);
	}
	cout << dp[2 * n];
	return 0;
}