HDU-4745 Two Rabbits 题解

题目大意

给你n个数，这n个数围成一个环，有两只兔子，可以从其中任意一个数出发，一个按顺时针跳跃，一个按逆时针跳跃，但是他们需要站在相同的数上，他们不能跳过已经被踩过的数字，并且他们能踩在同一个数上。问他们最多能跳几次。

解题思路

因为他们需要踩在相同的数字上，所以其实这就是一个最长回文子序列的问题。

（真的难想。。

求最长回文子序列很简单，看代码就懂了。

for (int len = 2; len <= n; len++) {
			for (int l = 1; l <= n - len + 1; l++) {
				int r = l +len - 1;
				if (num[l] == num[r])	dp[l][r] = max(dp[l][r], dp[l + 1][r - 1] + 2);
				else dp[l][r] = max(dp[l + 1][r], dp[l][r - 1]);
			}
		}

枚举长度，得到左右端点，如果左右两端相同，那就是中间区间的最长值加2,。

如果不相同，那要么就是左边区间添加了j，要么就是右边区间添加了i，去其中的最大值。

我们用$dp[l][r]$表示l到r的最长回文子序列长度。

有两种思路。

1、我们可以在1-n区间中枚举一个点i，那么就分为了$[1,i]$和$[i+1,n]$。

假设$[1,i]$中最长的回文子序列为$[x,y]$，$[i+1,n]$中最长的回文子序列为$[x_1,y_1]$。

那么一个人的路径为$x->y,x_1->y_1$，另外一个人的路径为$y->x,y_1->x_1$。

答案为$max(dp[1][i],dp[i+1][n])$。

2、因为是一个环，可以使用倍增的思路，将数组扩大两倍。

由题意可知，每一个人最多走n步。

所以只需要找到长度为n的最长回文子序列即可，这时候每个人从这个最长回文子序列的两端开始跳跃。

但是有一种特殊情况，当两点重合的时候，也就是从同一点出发时，这个时候找的就是长度为n-1的最长回文子序列，并且答案需要加1。

比如1121，我们同时以1为起点，然后$1->2->1$，答案为4。

也就是，起点可以不构成回文子序列。

答案为$max(dp[i][i+n-1],dp[i][i+n-2]+1)$。

（dp怎么这么难。。

完整代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 2200;
int num[N], dp[N][N];

int main() {
	int n;
	while (cin>>n&&n) {
		for (int i = 1; i <= n; i++)	
			cin >> num[i], num[n + i] = num[i];
		memset(dp, 0, sizeof(dp));
		for (int i = 1; i <= n; i++)	dp[i][i] = 1;
		for (int len = 2; len <= n; len++) {
			for (int l = 1; l <= 2 * n - len + 1; l++) {
				int r = l +len - 1;
				if (num[l] == num[r])	dp[l][r] = max(dp[l][r], dp[l + 1][r - 1] + 2);
				else dp[l][r] = max(dp[l + 1][r], dp[l][r - 1]);
			}
		}
		int ans = 0;
		for (int i = 1; i <= n; i++) {
			ans = max(ans, dp[i][i + n - 1]);
			ans = max(ans, dp[i][i + n - 2] + 1);
		}
		cout << ans << endl;
	}
}