bzoj1978 [BeiJing2010]取數遊戲 game dp

Description

小 C 剛學了輾轉相除法，正不亦樂乎，這小 P 又出來搗亂，給小 C 留了個 難題。 給 N 個數，用 a1,a2…an來表示。現在小 P 讓小 C 依次取數，第一個數可以 随意取。假使目前取得 aj，下一個數取ak(k>j)，則ak必須滿足gcd(aj,ak)≥L。 到底要取多少個數呢？自然是越多越好！ 不用多說，這不僅是給小 C 的難題，也是給你的難題。

2≤L≤ai≤1 000 000；

30% 的資料N≤1000；

100% 的資料 N≤50 000

Solution

考慮dp，設f[i]表示第i位一定選的最長答案，n^2轉移非常naive

因為gcd(a[j],a[i])|a[i]，是以我們可以記錄last[x]表示最大的j使得x|a[j]，然後枚舉a[i]的因數作為gcd用last更新答案，這樣是n√n的

Code

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)

const int N=;

int a[N],f[N],last[];

int main(void) {
    int n,m,ans=; scanf("%d%d",&n,&m);
    rep(i,,n) scanf("%d",&a[i]);
    rep(i,,n) { f[i]=;
        for (int j=;j*j<=a[i];j++) {
            if (a[i]%j) continue;
            if (j>=m) f[i]=std:: max(f[i],f[last[j]]+);
            if (a[i]/j>=m) f[i]=std:: max(f[i],f[last[a[i]/j]]+);
            last[j]=last[a[i]/j]=i;
        }
        ans=std:: max(f[i],ans);
    }
    printf("%d\n", ans);
    return ;
}