641div2 - B. Orac and Models

联想到最长递增序列，很快想到此题的dp，不过中间犯了两个错误。
一开始设dp[i]: 到i为止符合条件的最大序列数目，则

这个公式不对，原因在于dp[i]和dp[k]表示的意义不一样，dp[k]表示以k结尾的符合条件的最大序列数目。
因此重新设dp[i]: 以i结尾的符合条件的最大序列数目，则

最后选择dp[1]到dp[n]中的最大者即可，代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
using ll = long long;
int t, n;
int s[N];
int dp[N];
int main() {
    std::ios::sync_with_stdio(false);
    cin>>t;
    while(t--) {
        cin >> n;
        for(int i=1; i<=n; i++) {
            cin >> s[i];
        }
        memset(dp, 0, sizeof(dp));
        for(int i=1; i<=n; i++) {
            dp[i] = 1;
        }
        // 超时dp
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=i/2; j++) {
               if(i%j==0 && s[i]>s[j]) {
                   dp[i] = max(dp[i], dp[j]+1);
               } 
            }
        }
        int ans = 0;
        for(int i=1; i<=n; i++) {
            ans = max(ans, dp[i]);
        }
        cout << ans << endl;     
    }
    return 0;
}

结果超时，因复杂度O(n²)，怎么能缩小j的范围呢？要保证j能整除i，是否可以让j以i, 2i, 3i...的方式循环？答案可以，正着推即可，代码如下：

       for(int i=1; i<=n; i++) {
           for(int j=i*2; j<=n; j+=i) {
               if(s[j]>s[i]) {
                   dp[j] = max(dp[j], dp[i]+1);
               }
           }
       

复杂度O()。