前言

笔记

前提(i, j  a， j > i）(dp[i] 为以i结尾的最大长度)

80分代码

没有进行因子分解的优化，直接枚举导致超时

#include<iostream>
#include<cstdio>
#include<cstring> 
using namespace std;

int t, n, mx;
const int N = 1e5 + 5;
int a[N], dp[N], ans;
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        ans = 1;
        scanf("%d", &n);
        memset(a, 0, sizeof(a));
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; i++)
        {
            int x;
            scanf("%d", &x);
            a[x] = 1;
            mx = max(mx, x);
        }
        for(int i = 1; i <= mx; i++)
        {
            if(a[i]) dp[i] = max(dp[i], 1);
                else continue;
            int temp = i;
            for(int z = 2; z <= temp; z++)
            {
                if(temp % z == 0)// 找到质因子 开始i->j 的转移
                {
                    for(int j = i + z; j <= mx; j += z)
                    {
                        if(a[j]){dp[j] = max(dp[j], dp[i] + 1);ans = max(dp[j], ans); break;}
                    }
                }
                else continue;
                while(temp % z == 0)
                temp /= z;
            }
        }
        cout << ans << endl;
    }
    

    return 0;
}

AC代码

#include<iostream>
#include<cstdio>
#include<cstring> 
using namespace std;

int t, n, mx;
const int N = 1e5 + 5;
int a[N], dp[N], ans;
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        ans = 1;
        scanf("%d", &n);
        memset(a, 0, sizeof(a));
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; i++)
        {
            int x;
            scanf("%d", &x);
            a[x] = 1;
            mx = max(mx, x);
        }
        //对于每个优秀的i -> j 转移 条件是 j是i中每个质因子的最小倍数   
        //状态转移方程 (dp[j] = max dp[i] + 1)
        // 1.枚举i 找质因子
        // 2. 找到j转移
        for(int i = 1; i <= mx; i++)
        {
            if(a[i]) dp[i] = max(dp[i], 1);
                else continue;
            int temp = i;
            for(int z = 2; z * z <= temp; z++)
            {
                if(temp % z == 0)// 找到质因子 开始i->j 的转移
                {
                    for(int j = i + z; j <= mx; j += z)
                    {
                        if(a[j]){dp[j] = max(dp[j], dp[i] + 1);ans = max(dp[j], ans); break;}
                    }
                }
                else continue;
                while(temp % z == 0)
                temp /= z;
            }
            if(temp > 1))//剩下了个大于根号的质数
            {
                for(int j = i + temp; j <= mx; j += temp)
                {
                    if(a[j]){dp[j] = max(dp[j], dp[i] + 1);ans = max(dp[j], ans); break;}
                            }
                        }
          }
        cout << ans << endl;
    }


    return 0;
}