codeforces 264B B. Good Sequences(dp+数论)

题目链接：

codeforces 264B

题目大意：

给出n个数，利用这n个数构造一个好的序列，好的序列是单调增的，而且序列中相邻的两个元素都不互质，问最长的好序列的长度是多少。

题目分析：

• 首先我们定义状态dp[i]表示当前的数进行构造的序列末尾的数的质因数包含i的时候的最长的情况。
• 然后我们从小到大枚举给出的每一个数，每次转移就是对于当前枚举的数，分解质因数，然后找到所有的dp[i]（i为当前数的质因数中最大的），然后更新它所有的质因数i的dp[i]为前面找到的最大值加1，然后利用最后一个数更新后的dp[i]数组记录的就是利用所有给出的数得到的末尾的数包含i这个质因子时的最优答案，统计所有答案中最优的即可。

AC代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX 100007

using namespace std;

int a[MAX];
int dp[MAX];
int ans,n;
bool prime[MAX];

void init ( )
{
    memset ( prime , true , sizeof ( prime ) );
    prime[0] = prime[1] = false;
    for ( int i = 2 ; i*i < MAX ; i++ )
    {
        if ( !prime[i] ) continue;
        for ( int j = i*i ; j < MAX ; j += i )
            prime[j] = false;
    }
}


int main ( )
{
    init ( );
    while ( ~scanf ( "%d" , &n ) )
    {
        memset ( dp , 0, sizeof ( dp ) );
        for ( int i = 0 ; i < n ; i++ )
            scanf ( "%d" , &a[i] );
        ans = 0;
        if ( n == 1 )
        {
            puts ("1" );
            continue;
        }
        for ( int i = 0 ; i < n ; i++ )
        {
            int temp = 0;
            int x = a[i];
            for ( int j = 2 ; j*j <= x ; j++ )
            {
                if ( x%j ) continue;
                if ( !prime[j] ) continue;
                while ( x%j == 0 )
                    x /= j;
                temp = max ( temp , dp[j]+1 );
            }
            if ( x > 1 ) temp = max ( temp , dp[x]+1 );
            x = a[i];
            for ( int j = 2 ; j*j <= x ; j++ )
            {
                if ( x%j ) continue;
                if ( !prime[j] ) continue;
                while ( x%j == 0 )
                    x /= j;
                dp[j] = temp;
            }
            if ( x > 1 ) dp[x] = temp;
            ans = max ( temp , ans );
        }
        printf ( "%d\n" , ans );
    }
}