本文共 909 字，大约阅读时间需要 3 分钟。

题目链接：

题目大意：

给出一个序列，求最长的子序列，满足隔位的两个数相等，问这个最长的子序列的长度是多少。

题目分析：

• 定义状态dp[i][j]代表以第i个数为末尾，第j个数为倒数第二个的情况下的最长子序列。
• 转移的方法很简单：
  dp[i][j]=dp[j][k]+1(a[k]==a[i])
  $$dp[i][j] = dp[j][k] +1 (a[k] == a[i])$$
• 其中k的找法很简单，直接在转移的过程中顺便找与a[i]相等的比当前位小的最大的那个。

  ---

AC代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #define MAX 4007using namespace std;int dp[MAX][MAX];int a[MAX],n;int main ( ){    while ( ~scanf ( "%d" , &n ) )    {        for ( int i = 1 ;i <= n ; i++ )            scanf ( "%d" , &a[i] );        int ans = 1;        for ( int i = 1 ; i <= n ; i++ )        {            int k = -1;            for ( int j = 1 ; j < i ; j++ )            {                if ( k == -1 )                    dp[i][j] = 2;                else                    dp[i][j] = dp[j][k] + 1;                if ( a[j] == a[i] )                     k = j;                ans = max ( ans , dp[i][j] );            }          }        printf ( "%d\n" , ans );    }}
      
     
    
   

转载地址：http://jqvjn.baihongyu.com/