题目大意:一组数按照顺时针排列,数值相同的两个位置可以连一条线,最终线与线不交叉的最大数量为多少。
这道题目是求最大匹配的题目,初学区间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;
}
}
版权声明:本文为u013611908原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。