HDU 4745 最长回文子序列

题目大意

两只青蛙朝不同方向条，每次都到达值相同的位置，不能重复到达自己到过的地方，且不能飞跃已到过的地方

我们可以理解为这两只青蛙分别把整个序列遍历了一遍，依次走过所有的点，找到最多相同的点的个数，因为朝不同方向，且形成环，所以可以把数组扩大两倍，写两组一样的数组

每次跳完得到的必然可以理解为是一个回文子序列

这里有个例外，就是在已形成的回文子序列下要是还有多出的点是可以加一的，因为可以令两只青蛙同时在这一点出发再去遍历回文串

DP过程

//DP过程是先从前后两个数距离范围最小的1开始，不断扩大距离，这样可以利用前面小范围来更新大范围
        //i在这里可以理解为2个数的距离
        for(int i=1;i<n;i++){
            for(int j=1;j<=n;j++){
                if(a[j] == a[j+i]){
                    dp[j][j+i] = max(dp[j+1][i+j-1]+2,dp[j][j+i]);
                }
                else
                    dp[j][j+i] = max(dp[j+1][j+i],dp[j][j+i-1]);
            }
        }

然后在范围为n-1的dp值中找最大值

和n-2的范围的dp+1中找最大值

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int N = ;

 int a[N],n;

 int dp[N][N];

 int main()

 {

     while(~scanf("%d",&n)){

         if(n==)

             break;

         for(int i=;i<=n;i++){

             scanf("%d",a+i);

             a[n+i] = a[i];

         }

         memset(dp,,sizeof(dp));

         for(int i=;i<=*n;i++)

             dp[i][i] = ;

        //DP过程是先从前后两个数距离范围最小的1开始，不断扩大距离，这样可以利用前面小范围来更新大范围

         //i在这里可以理解为2个数的距离

         for(int i=;i<n;i++){

             for(int j=;j<=n;j++){

                 if(a[j] == a[j+i]){

                     dp[j][j+i] = max(dp[j+][i+j-]+,dp[j][j+i]);

                 }

                 else

                     dp[j][j+i] = max(dp[j+][j+i],dp[j][j+i-]);

             }

         }

         int maxn = ;

         for(int i=;i<=n;i++)

             maxn = max(maxn,dp[i][i+n-]);

         for(int i=;i<=n;i++)

             maxn=max(maxn,dp[i][i+n-]+);

         printf("%d\n",maxn);

     }

     return ;

 }

巴特西

HDU 4745 最长回文子序列

最新文章

热门文章