HDU ~ 4745 ~ Two Rabbits (区间DP,环形序列的最长回文子序列)
题意
有两只兔子和一个N块石头组成的环,他们在这个环跳,A顺时针跳,B逆时针跳,有一个要求他们两个每时每刻必须站在相同质量的石头上,跳过的石头不能再跳,两个人的起点任意(可以相同),求两只兔子步数之和的最大值?
思路
问题就相当于:环形序列的最长回文子序列。环形序列,其实我们把原串往后复制一段就OK了。
表示区间的最优解,状态转移方程为:
①,
②,
注意:起点可以一样
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e3 + 5;
int n, a[MAXN], dp[MAXN][MAXN];
int main()
{
while (~scanf("%d", &n) && n)
{
for (int i = 0; i < n; i++) scanf("%d", &a[i]), a[i + n] = a[i];
memset(dp, 0, sizeof(dp));
for (int i = 0; i < 2 * n; i++) dp[i][i] = 1;
for (int len = 2; len <= n; len++)
{
for (int i = 0; i + len - 1 < 2 * n; i++)
{
int j = i + len - 1;
if (a[i] == a[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
int ans = 0;
for (int i = 0; i < n; i++)
{
ans = max(ans, dp[i][i + n - 1]);
ans = max(ans, dp[i][i + n - 2] + 1);
}
printf("%d\n", ans);
}
return 0;
}
/*
1
1
4
1 1 2 1
6
2 1 1 2 1 3
0
*/