HDU 4745 Two Rabbits
题目分析
这个题目乍一看觉得很麻烦，不过仔细读题就会发现一个重要的条件：两个兔子不会相互穿过，也就是说，两个兔子始终在一个环里面走；而且在任意时刻，两个兔子所在的位置的权值一样，那么我们设想一下两个兔子都从终点出发，看他们最远可以走多少步，这样等价于两个兔子从任意位置出发最后聚集于同一个位置一样；
那么我们从终点走的时候，两个兔子走过的石子的权值恰好构成一个回文串。
这样一来我们所求的就变成了求给定的环中最长的回文子序列了。
现在讲一下下面代码的思想吧，我们记dp [ i ] [ j ] 为从 i - j 的最长回文子序列的长度，先求出了所有子序列的回文长度，具体做法：
首先说明一下代码： dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
现在我们需要求的是区间 [ i, j ] 的最长回文子序列，如图
那么这个区间的最长回文子串可能是由区间 [ i+1 , j ] 的左边添加一个元素后形成的，为了不打乱 [ i + 1 , j ] 中的最长回文子序列，我们把添加的元素不计入回文串的计算就好。
同理，这个区间的最长回文子串也可能是在区间 [ i , j - 1] 的右边添加一个元素后形成的，为了不打乱 [ i , j - 1 ] 中的最长回文子序列，我们把添加的元素不计入回文串的计算就好。
然后就是代码: if (w[i] == w[j]) dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + 2);
除去上面两种得到当前区间最长回文子串的方法外，还有一种情况，那就是当 w[i] == w[j] 的时候，我们可以在原区间 [ i + 1 , j -1 ] 的基础上使得区间 [ i+1, j -1 ] 的最长回文子串添加了 i,j 后 长度 加 2 得到了区间 [ i, j ] 的最长回文子串
这样，我们就求出了区间 [ 1 , n ] 所有子串的最长回文子串。
下面解释一下代码：for (int i = 1; i <= n; i++) ans = max(dp[1][i] + dp[i + 1][n], ans);
在这里我们枚举所有的石子作为两个区间的分隔点 i ，使得分隔点左边区间 [ 1, i ] 的最长回文子串的长度加上右边区间 [ i +1 ,n ] 的最长回文子串的长度，求出这个和的最大值，即为我们所求的答案。我们来解释一下原理：
我们画出了这个的示意图，由图我们很清晰的看出来 ，兔子1 和兔子2走的路是一样的，而且他们所走的路程之和就是 区间[ 1, i ] 和 [ i+1, n ] 的最长回文串的长度之和，这里，其实理解了两只兔子是如何行走的，就可以理解这个代码的意思了
代码区
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const int Max = 1e3 + 10;
const int inf = 0x3f3f3f3f;
using namespace std;
int dp[Max][Max];//dp[i][j]从i -> j 的最长回文子序列长度
int w[Max]; //石子权值
int main()
{
std::ios::sync_with_stdio(false);
int n;
while(cin>>n && n)
{
for(int i = 1 ; i <= n ; i++)
{
cin >> w[i];
}
for(int i = 1 ; i <= n ; i++)
{
for(int j = 1; j<= n ; j++)
{
if(i == j)
{
dp[i][j] = 1;
}
else
{
dp[i][j] = 0;
}
}
}
for(int i = n-1 ; i > 0 ; i--)
{
for(int j =i +1 ; j <= n ; j++)
{
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
//从[i-j]的子区间[i+1,j] [i,j-1]转移而来
if (w[i] == w[j]) dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + 2);
//区间两边相同，判断区间[i+1,j] [i,j-1]的最大回文串子串和[i+1,j-1]+2的最大回文串子串的长度
}
}
int ans = 0;
for (int i = 1; i <= n; i++) ans = max(dp[1][i] + dp[i + 1][n], ans);//两只兔子分别以[1,i]的中心位置出发，走到[i+1,n]的中心位置
cout << ans << endl;
}
return 0;
}