博客

题目大意：一组数按照顺时针排列，数值相同的两个位置可以连一条线，最终线与线不交叉的最大数量为多少。

这道题目是求最大匹配的题目，初学区间DP，脑子一片空白，仅仅记下来，以供之后温习。

按照区间的想法可以很容易的得到，dp[i][j]所存的是i到j当中满足条件的最大数值，那么有dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);

这个是解决在i到j区间当中有两部分连线互相不包含也不想交，则最大值便是两者相交。

但这种方法没办法解决两头可以相连的情况，这是最基础的情况，所以在一开始便有dp[i][j]=dp[i+1][j-1]+(a[i]==a[j]);

AC代码：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[1100];
int dp[1100][1100];
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &a[i]);
			dp[i][i] = 0;
		}
		for (int i = 1; i <= n; i+=2)
		for (int j = 1; j+i<=n;j++)
		{
			int end = j + i;
			dp[j][end] = dp[j + 1][end - 1] + (a[j] == a[end]);
			for (int k = j; k < end; k++)//解决不是回文结构，即两部分加起来
				dp[j][end] = max(dp[j][end], dp[j][k] + dp[k + 1][end]);
		}
		cout << dp[1][n] << endl;
	}
}