5.13 每日一题题解

Orac and Models

• 题目链接：http://codeforces.com/contest/1350/problem/B

涉及知识点：

• 简单dp

solution：

• (让你找出一个序列使得他在原序列满足以下条件)
• (i是j的倍数 且 a[i]>a[j],问最长的序列长度)
• (我们只要枚举第一个下标i，令j每次不断加i，这样保证j永远是i的倍数)
• (新开一个dp数组，dp[i]表示以a[i]结尾的最长序列长度)
• (复杂度n*sqrt{n})

std:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 200005;
int a[maxn],dp[maxn];
int main()
{
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            dp[i] = 1;
        }
        for(int i=1;i<=n;i++){
            for(int j=i*2;j<=n;j+=i){
                if(a[i] < a[j])
                    dp[j] = max(dp[j] , dp[i] + 1);
            }
        }
        int ans = 0;
        for(int i=1;i<=n;i++)ans = max(ans , dp[i]);
        cout<<ans<<endl;
    }
    
    return 0;
}