HDU 4745 Two Rabbits (最长回文变形)
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
http://acm.hdu.edu.cn/showproblem.php?pid=4745
/*31ms,4192KB*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mx = 1005;
int dp[mx][mx];///从i到j的最长回文串的长度
int w[mx];
int solve(int n)
{
int i, j;
memset(dp, 0, sizeof(dp));
for (i = 1; i <= n; ++i) dp[i][i] = 1;
for (i = n - 1; i; --i)
for (j = i + 1; j <= n; ++j)
if (w[i] == w[j]) dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + 2);
else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
///枚举起点。针对每个起点,两边的最长回文串的长度之和就是从这里出发的最大值
///注意把[1,n]区间也算上
int ans = 0;
for (i = 1; i <= n; ++i) ans = max(ans, dp[1][i] + dp[i + 1][n]);
return ans;
}
int main()
{
int n, i;
while (scanf("%d", &n), n)
{
for (i = 1; i <= n; ++i) scanf("%d", &w[i]);
printf("%d\n", solve(n));
}
return 0;
}
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |