HDU 4745 Two Rabbits(非連續最長回文子序列，區間DP)

HDU 4745 Two Rabbits(非連續最長回文子序列，區間DP)

HDU 4745 Two Rabbits

題目地址

題意：
兩只兔子，在n塊圍成一個環形的石頭上跳躍，每塊石頭有一個權值ai，一只從左往右跳，一只從右往左跳，每跳一次，兩只兔子所在的石頭的權值都要相等，在一圈內（各自不能超過各自的起點，也不能再次回到起點）它們最多能經過多少個石頭(1 <= n <= 1000, 1 <= ai <= 1000)。

分析：
其實就是求一個環中，非連續最長回文子序列的長度。
dp[i][j] = max{ dp[i + 1][j], d[i][j - 1], (if a[i] == a[j]) dp[i + 1][j - 1] + 2 }
但是，這個dp公式僅僅是求出一個序列的非連續最長回文子序列，題目的序列是環狀的，有兩種思路：

1. 將環倍增成鏈，求出窗口為n的最長子序列，但這不是最終的解，你可以試看看Sample 2,是只能得出4,因為它在選中的回文外面還可以選中一個當做起點來跳，所以外面得判斷找出來的回文外面是否還有可以當起點的石頭，即可以找窗口為(n-1)的長度+1。所以解即找 窗口為n的長度或者 窗口為(n-1)的長度+1 的最大值。

2. 不倍增，直接當成一個鏈求dp，然後把鏈切成兩半，求出兩邊的回文長度，最大的和就是解。這裡不用考慮起點問題，因為兩邊的回文中點都可以做起點。

   CODE：
   解法1：

   /*
   *  Author:      illuz 
   *  Blog:        http://blog.csdn.net/hcbbt
   *  File:        4745.cpp
   *  Create Date: 2014-02-06 13:39:27
   *  Descripton:  dp 
   */
   
   #include 
   #include 
   #include 
   #include 
   using namespace std;
   
   const int N = 1001<<1;
   
   int dp[N][N];
   int a[N];
   int n;
   
   int main() {
   	while (scanf("%d", &n) && n) {
   		for (int i = 1; i <= n; i++) {
   			scanf("%d", &a[i]);
   			a[n + i] = a[i];
   		}
   
   		memset(dp, 0, sizeof(dp));
   		for (int i = 1; i <= 2 * n; i++)
   			dp[i][i] = 1;
   
   		for (int len = 1; len < 2 * n; len++) {
   			for (int i = 1; i + len <= 2 * n; i++) {
   				int j = i + len;
   				dp[i][j] = max(dp[i + 1][j], max(dp[i][j - 1], (a[i] == a[j] ? dp[i + 1][j - 1] + 2 : 0)));
   			}
   		}
   
   		int ans = 0;
   		for (int i = 1; i <= n; i++)
   			ans = max(ans, dp[i][i + n - 1]);
   		for (int i = 1; i <= n; i++)
   			ans = max(ans, dp[i][i + n - 2] + 1);
   		printf("%d\n", ans);
   	}
   	return 0;

   
   
   

   解法2：

   /*
   *  Author:      illuz 
   *  Blog:        http://blog.csdn.net/hcbbt
   *  File:        4745.cpp
   *  Create Date: 2014-02-06 13:39:27
   *  Descripton:  dp 
   */
   
   #include 
   #include 
   #include 
   #include 
   using namespace std;
   
   const int N = 1001;
   
   int dp[N][N];
   int a[N];
   int n;
   
   int main() {
   	while (scanf("%d", &n) && n) {
   		for (int i = 1; i <= n; i++)
   			scanf("%d", &a[i]);
   
   		memset(dp, 0, sizeof(dp));
   		for (int i = 1; i <= n; i++)
   			dp[i][i] = 1;
   
   		for (int len = 1; len < n; len++) {
   			for (int i = 1; i + len <= n; i++) {
   				int j = i + len;
   				dp[i][j] = max(dp[i + 1][j], max(dp[i][j - 1], (a[i] == a[j] ? dp[i + 1][j - 1] + 2 : 0)));
   			}
   		}
   
   		int ans = 0;
   		for (int i = 1; i <= n; i++)
   			ans = max(ans, dp[1][i] + dp[i + 1][n]);
   		printf("%d\n", ans);
   	}
   	return 0;
   }

   
   
   

   總結：
   遇到環首先考慮拆成鏈或者dp。