【CF 1350 B.Orac and Models】 DP

Orac and Models

题意

给出包含n个数字的数组(s)，现在让你选出最长的一个子序列，

(i_j)表示子序列中第j个数字在s中的下标，要满足(s_{i_j}<s_{i_{j+1}})，

以及(i_j)是(i_{j+1})的因子。

思路

类似于最长递增子序列，(dp[i])表示以第i个数字为子序列的结尾最多有多少数字。

转移方程：(dp[i]=max(dp[i],dp[j]+1)),i%j==0,s[j]<s[i]

具体实现的时候从j推i，复杂度是(n/1+n/2+n/3+n/4+...)

大概就是(nlogn)

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
typedef long long ll;
typedef unsigned long long ull;

int dp[N],arr[N];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&arr[i]);
            dp[i]=1;
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=i; j<=n; j+=i)
            {
                if(arr[i]<arr[j])
                    dp[j]=max(dp[j],dp[i]+1);
            }
        }
        int ans=0;
        for(int i=1; i<=n; i++)
            ans=max(ans,dp[i]);
        printf("%d
",ans);
    }
    return 0;
}