hdu - 4745 - Two Rabbits
题意:两只兔子,在n块围成一个环形的石头上跳跃,每块石头有一个权值ai,一只从左往右跳,一只从右往左跳,每跳一次,两只兔子所在的石头的权值都要相等,在一圈内(各自不能超过各自的起点,也不能再次回到起点)它们最多能经过多少个石头(1 <= n <= 1000, 1 <= ai <= 1000)。题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4745
——>>模拟样例后,初看挺像欧拉回路,接着同学说应是最长公共子序列LCS,接着就惨了,一直到比赛Ended都TLE……
原来,只是简单的dp求最长回文子序列……
假设一个有11个数的序列:1 2 3 4 3 2 1 8 9 9 8
假设在第7个数后切开,前7个是一个回文序列,后4个也是一个回文序列,那么,不妨从左边回文串的中心开始,一个顺时针,一个逆时针,模拟一下就会发现,答案就是:枚举切线,左边最大回文子序列的长度加上右边回文子序列的长度的最大值。
#include <cstdio> #include <algorithm> using namespace std; const int maxn = 1000 + 10; int n, a[maxn], d[maxn][maxn]; void read(){ for(int i = 1; i <= n; i++) scanf("%d", &a[i]); } void solve(){ for(int i = 1; i <= n; i++) d[i][i] = 1; for(int len = 2; len <= n; len++) for(int i = 1; i <= n-len+1; i++){ int j = i + len - 1; if(a[i] == a[j]) d[i][j] = d[i+1][j-1] + 2; else d[i][j] = max(max(d[i+1][j], d[i][j-1]), d[i+1][j-1]); } int Max = -1; for(int i = 1; i <= n; i++) Max = max(Max, d[1][i] + d[i+1][n]); printf("%d\n", Max); } int main() { while(scanf("%d", &n) == 1 && n){ read(); solve(); } return 0; }
补充:软件开发 , C++ ,