C - Two Rabbits https://vjudge.net/problem/HDU-4745
这个题目的意思是, n 块石头围一圈. 一只兔子顺时针, 一只兔子逆时针 (限制在一圈的范围内).
这个题目我觉得还比较难, 不太好想, 不过后来 lj 大佬给了我一点点提示, 因为是需要跳到相同的重量的石头上去,
所以这个就和回文序列有关系了, 我也明白和回文序列有关系了, 因为他们是不同方向的, 而且又要跳到相同重量的石头上去,
所以这个就说明我需要找一段回文序列, 找到的这段回文序列的长度就是兔子可以跳的长度, 所以我们应该求这一段区间的最长回文子序列.
但是注意, 这个和普通的回文不太一样, 就是普通的回文我们需要的是最长回文子串, 这个我们只需要最长回文子序列, 意思就是说可以跳过一部分石头.
知道这个之后, 其实我还是不太会处理这个环状的回文子序列, 然后又看了一下题解, 说可以把环变成链,
其实这种处理方式之前见过, 不过一下子没有反应过来, 处理完这个之后, 就是来进行区间 dp, 求一个区间的最长的回文子序列.
这个有了区间 dp 之后其实还比较好求, 因为不是一定要挨在一起, 所以就定义 dp[i][j] 表示从 i 到 j 的最长的回文子序列.
转移方程就是 if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]+2 else dp[i][j]=max(dp[i+1][j],dp[i][j-1])
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <queue>
- #include <algorithm>
- #include <vector>
- #include <iostream>
- #define inf 0x3f3f3f3f
- using namespace std;
- const int maxn = 1010;
- int dp[2*maxn][2*maxn];
- int a[maxn*4];
- int main()
- {
- int n;
- while(scanf("%d",&n)!=EOF&&n)
- {
- memset(dp, 0, sizeof(dp));
- for(int i=1;i<=n;i++)
- {
- scanf("%d", &a[i]);
- dp[i][i] = 1;
- a[i + n] = a[i];
- }
- int ans = 1;
- for(int i=2;i<=n;i++)
- {
- for(int j=1;j+i-1<=2*n;j++)
- {
- int ends = j + i - 1;
- if (a[j] == a[ends]) dp[j][ends] = dp[j + 1][ends - 1] + 2;
- else dp[j][ends] = max(dp[j + 1][ends], dp[j][ends - 1]);
- ans = max(ans, dp[j][ends]);
- }
- }
- for(int i=1;i<=n;i++)
- {
- ans = max(ans, dp[i][i + n - 1]);
- ans = max(ans, dp[i][i + n - 2] + 1);
- }
- printf("%d\n", ans);
- }
- return 0;
- }
区间 dp
来源: http://www.bubuko.com/infodetail-3075172.html