Codeforces Round #641 div2 B. Orac and Models (DP)

题意:有一个长度为\(n\)的序列\(a\),求一个最长上升子序列,且这个子序列的元素在\(a\)中的位置满足\(i_{j+1}modi_{j}=0\),求这个子序列的最大长度.
题意:这题假如我们用\(O(n^2)\)的朴素DP来求肯定是会TLE的,我们在原有的方法上做一些优化.

我们首先遍历\(a\),确定子序列的首位置,然后我们知道下一个能取的位置至少是\(2*i\),然后每次\(j+=i\)向后遍历求一个LIS即可.

代码:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <stack>

#include <queue>

#include <vector>

#include <map>

#include <set>

#include <unordered_set>

#include <unordered_map>

#define ll long long

#define fi first

#define se second

#define pb push_back

#define me memset

const int N = 1e6 + 10;

const int mod = 1e9 + 7;

using namespace std;

typedef pair<int,int> PII;

typedef pair<long,long> PLL;

int t;

int n,a[N];

int dp[N];

int main() {

    ios::sync_with_stdio(false);

    cin>>t;

     while(t--){

         cin>>n;

          for(int i=1;i<=n;++i) cin>>a[i];

          for(int i=1;i<=n;++i) dp[i]=1;

          int ans=0;

          for(int i=1;i<=n;++i){

              for(int j=i*2;j<=n;j+=i){

                  if(a[j]>a[i]) dp[j]=max(dp[j],dp[i]+1);

              }

              ans=max(ans,dp[i]);

          }

         printf("%d\n",ans);

     }

    return 0;

}

巴特西

Codeforces Round #641 div2 B. Orac and Models (DP)

最新文章

热门文章