本文主要是介绍hdu 4745 - Two Rabbits(动规)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
比赛的时候一直磕到lcs上，怎么优化都不能过掉这道题目，，，，
气死个人，，，
听了人家的找区间回文串的思路，才恍然大悟啊。。。
状态：dp[i][j]表示i,,,j组成的子串中的最长回文串的长度
状态转移：dp[i][j] = max{dp[i+1][j], dp[i][j-1], dp[i+1][j-1]+2*(s[i]==s[j])};
代码如下：
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <map>#define M 1005
#define INF 0x7fffffff
#define eps 1e-8
#define LL long long
#define LLU unsigned long longusing namespace std;vector<int>vec[M];
int n, a[M], dp[M][M];int main ()
{while(scanf("%d", &n) && n){for(int i = 0; i <= 1000; ++i)vec[i].clear();for(int i = 0; i < n; ++i){scanf("%d", &a[i]);vec[a[i]].push_back(i);}if(n==1){printf("1\n");continue;}for(int i = 0; i < n; ++i)dp[i][i] = 1;for(int i = 0; i < n; ++i){if(a[i]==a[i+1]) dp[i][(i+1)%n] = 2;else dp[i][(i+1)%n] = 1;}for(int len = 3; len <= n; ++len){for(int i = 0; i < n; ++i){int j = (i+len-1)%n;dp[i][j] = max(dp[(i+1+n)%n][j], dp[i][(j-1+n)%n]);dp[i][j] = max(dp[i][j], (dp[(i+1+n)%n][(j-1+n)%n]+(a[i]==a[j]?2:0)));}}int ans = 0;for(int i = 0; i <= 1000; ++i){for(int j = 0; j < (int)vec[i].size(); ++j)for(int k = 0; k < (int)vec[i].size(); ++k){if(j==k) ans = max(ans, dp[(vec[i][j]+1)%n][(vec[i][j]-1+n)%n]+1);else ans = max(ans, dp[vec[i][j]][vec[i][k]]+dp[vec[i][k]][vec[i][j]]-2);}}printf("%d\n", ans);}return 0;
}
这篇关于hdu 4745 - Two Rabbits(动规)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
