Codeforces Round #641(Div.2) Orac and Models 최장 상승 하위 시퀀스의 변형

이 문제는 가장 긴 상승자 서열을 토대로 제한 조건을 더했다. 바로 이 상승자 서열의 원수 그룹 아래에 현재 이전에 제거될 수 있다는 것이다.사상은 역시 dp[i]가 i로 끝나는 만족 조건의 최장 상승 서열을 나타낸다. 일반적인 lst, dp[i]는 1~i-1에서 갱신을 받아야 하고 1~i-1의 dp값으로 dp[i]를 갱신하는 것으로 이해할 수 있다. 그러면 여기에 만족 조건의 하표를 일일이 열거하여 dp[i]를 갱신해야 한다. 즉, i라는 하표의 인자 하표를 에이치체로 하는 사상이다.

#pragma GCC optimize(2)
#include
using namespace std;
const int man = 2e5+10;
#define IOS ios::sync_with_stdio(0)
typedef long long ll;
const ll mod = 1e9+7;
int a[man],cnt[man];

int main() {
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        //freopen("out.txt","w",stdout);
    #endif
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        for(int i = 1;i <= n;i++){
            cin >> a[i];
            cnt[i] = 1;
        }
        int maxx = 1;
        for(int i = 1;i <= n;i++){
            for(int j = 2 * i;j <= n;j += i){
                if(a[j]>a[i])cnt[j] = max(cnt[j],cnt[i]+1);
            }
            maxx = max(maxx,cnt[i]);
        }
        cout << maxx << endl;
    }   
    return 0;
}