题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=4745
题目意思:
给n个环状的数,A、B两人沿相反的方向走,每单位时间走一步,要求相同时间两人到达相同的数,且同一位置同一个人不能走两次,走过的位置不能越过。
解题思路:
根据回文非连续序列的性质,从前往后,和从后往前序列是一样的,所以只用求出区间内最长的回文序列即可,又由于是环状,所以分成两部分,1~i i+1~n,A可以从i走到1,然后从n走到i+1,B可以从1走到i,从i+1走到n .
代码:
#include<iostream> #include<cmath> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<algorithm> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<ctime> #define eps 1e-6 #define INF 0x3fffffff #define PI acos(-1.0) #define ll __int64 #define lson l,m,(rt<<1) #define rson m+1,r,(rt<<1)|1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; #define Maxn 1100 int sa[Maxn]; int dp[Maxn][Maxn]; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int n; while(scanf("%d",&n)&&n) { memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { scanf("%d",&sa[i]); dp[i][i]=1; } for(int i=2;i<=n;i++) { for(int j=1;j+i-1<=n;j++) { int k=i+j-1; dp[j][k]=max(dp[j][k],max(dp[j+1][k],dp[j][k-1])); if(sa[j]==sa[k]) dp[j][k]=max(dp[j][k],dp[j+1][k-1]+2); } } int ans=0; for(int i=1;i<=n;i++) ans=max(ans,dp[1][i]+dp[i+1][n]); printf("%d ",ans); } return 0; }