hdu 4745 区间dp

题意：求一个环的最长回文序列，是序列不是串

链接：点我

起点是可以任意的，

所以只要求出每个区间的最长回文序列之后取max（dp[1][i]+dp[i+1][n]），即可得最终答案

本来是想扩展两倍的，但是后来的最大不太好想

将环倍增成链，求出窗口为n的最长子序列，但这不是最终的解，你可以试看看Sample 2,是只能得出4,因为它在选中的回文外面还可以选中一个当做起点来跳，所以外面得判断找出来的回文外面是否还有可以当起点的石头，即可以找窗口为(n- 1)的长度+1。所以解即找窗口为n的长度或者窗口为(n-1)的长度+1 的最大值。
不倍增，直接当成一个链求dp，然后把链切成两半，求出两边的回文长度，最大的和就是解。这里不用考虑起点问题，因为两边的回文中点都可以做起点。

Sample Input

1
1
4
1 1 2 1
6
2 1 1 2 1 3
0
Sample Output

1
4
5



2015-05-06 代码

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<queue>
 7 #include<map>
 8 using namespace std;
 9 #define MOD 1000000007
10 const int INF=0x3f3f3f3f;
11 const double eps=1e-5;
12 typedef long long ll;
13 #define cl(a) memset(a,0,sizeof(a))
14 #define ts printf("*****
");
15 const int MAXN=1005;
16 int n,m,tt;
17 int a[MAXN];
18 int dp[MAXN][MAXN];
19 int main()
20 {
21     int i,j,k;
22     #ifndef ONLINE_JUDGE
23     freopen("1.in","r",stdin);
24     #endif
25     while(scanf("%d",&n)!=EOF)
26     {
27         if(n==0)    break;
28         cl(dp);
29         for(i=0;i<n;i++)
30         {
31             scanf("%d",&a[i]);
32             dp[i][i]=1;
33         }
34         for(int len=1;len<n;len++)
35         {
36             for(i=0;i+len<n;i++)
37             {
38                 j=len+i;
39                 if(a[i]==a[j])  dp[i][j]=dp[i+1][j-1]+2;
40                 else dp[i][j]=max(dp[i][j-1],dp[i+1][j]);
41             }
42         }
43         int ans=0;
44         for(int i=0;i<n;i++)
45             ans=max(ans,dp[0][i]+dp[i+1][n-1]);
46         printf("%d
",ans);
47     }
48 }

View Code

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 int dp[1001][1001];
 6 int a[1001];
 7 int n;
 8 int main()
 9 {
10     while(scanf("%d",&n)&&n)
11     {
12         for(int i=1;i<=n;i++)
13             scanf("%d",&a[i]);
14         memset(dp,0,sizeof(dp));
15         for(int i=1;i<=n;i++)
16             dp[i][i]=1;
17         for(int len=1;len<n;len++) {
18             for (int i=1;i+len<=n;i++) {
19                 int j=i+len;
20                 if(a[i]==a[j])
21                     dp[i][j]=dp[i+1][j-1]+2;
22                 else
23                     dp[i][j]=max(dp[i][j-1],dp[i+1][j]);
24             }
25         }
26         int ans=0;
27         for(int i=1;i<=n;i++)
28             ans=max(ans,dp[1][i]+dp[i+1][n]);
29         printf("%d
",ans);
30     }
31     return 0;
32 }