(DP) bzoj 1978

1978: [BeiJing2010]取数游戏 game

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 729 Solved: 451
[Submit][Status][Discuss]

Description

小 C 刚学了辗转相除法，正不亦乐乎，这小 P 又出来捣乱，给小 C 留了个难题。给 N 个数，用 a1,a2…an来表示。现在小 P 让小 C 依次取数，第一个数可以随意取。假使目前取得 aj，下一个数取ak(k>j)，则ak必须满足gcd(aj,ak)≥L。到底要取多少个数呢？自然是越多越好！不用多说，这不仅是给小 C 的难题，也是给你的难题。

Input

第一行包含两个数N 和 L。接下来一行，有 N 个数用空格隔开，依次是 a1,a2…an。

Output

仅包含一行一个数，表示按上述取法，最多可以取的数的个数。

Sample Input

5 6
7 16 9 24 6

Sample Output

HINT

选取 3个数16、24、6。gcd(16,24)=8，gcd(24,6)=6。

2≤L≤ai≤1 000 000；
30% 的数据N≤1000；
100% 的数据 N≤50 000

pre[j]表示以j为公因子的坐标最大的数的位置。。。

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

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
int n,l;
int ans,dp[50005],pre[50005];
int main()
{
    int x;
    scanf("%d%d",&n,&l);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        for(int j=1;j<=sqrt(x);j++)
        {
            if(x%j==0)
            {
                if(j>=l)
                    dp[i]=max(dp[i],dp[pre[j]]+1),pre[j]=i;
                int k=x/j;
                if(k>=l)
                    dp[i]=max(dp[i],dp[pre[k]]+1),pre[k]=i;
            }
        }
        ans=max(ans,dp[i]);
    }
    printf("%d
",ans);
    return 0;
}