代码源每日一题div1 枚举倍数优美！最长上升子序列

悠悠 2024-03-31 12:47 21阅读 0赞

[优美！最长上升子序列 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge]

题意：

![6f04eef96ab64f4db0fd4e87ae511e95.png][]

思路：

在LIS的基础上，我们发现dp\[i\]除了得从比a\[i\]小的位置转移过来外，还得从 i 的约数 j 转移过来

因此我们可以去枚举约数

但是枚举约数的复杂度过高，是O(n根号n)，很容易超时

因此我们去先去枚举因子，再去枚举倍数，这样的复杂度是O(nlogn)

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=1e6+10;
    #define int long long
    int n;
    int a[mxn],dp[mxn];
    void solve(){
        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=-1;
        for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int T=1;
        cin>>T;
        while(T--)solve();
        return 0;
    }

**总结：**

**一般要做枚举约数的操作时，不妨去先枚举因子，再去枚举倍数，这样复杂度就从O(n根号n)变成O(nlogn)**

[- _ - Daimayuan Online Judge]: http://oj.daimayuan.top/problem/671
[6f04eef96ab64f4db0fd4e87ae511e95.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/806cb43703fe49fa820db875bea6b68c.png

发表评论取消回复

表情：

评论列表（有 0 条评论，21人围观）

还没有评论，来说两句吧...

相关阅读

相关代码源每日一题div1 枚举倍数优美！最长上升子序列

[优美！最长上升子序列 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意： ![6f04eef

悠悠/ 2024年03月31日 12:47/ 0 赞/ 22 阅读

相关代码源每日一题div1 枚举倍数平方计数

[平方计数 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意： ![4599c5d594734

小灰灰/ 2024年03月31日 12:35/ 0 赞/ 27 阅读

相关【代码源每日一题】最长有趣子序列

....为什么审核一直不过题意： ![4de6189cd74886d6881b1a6cb06d0d89.png][] 思路：感觉这道题我绝对写过啊，但是不知道为什么

我就是我/ 2024年03月26日 20:00/ 0 赞/ 43 阅读

相关【枚举+数学】代码源每日一题div2 数学

[数学 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意： ![d1eee51010a84b5

清疚/ 2024年03月16日 18:42/ 0 赞/ 8 阅读

相关最长上升子序列

最长上升子序列 1、参考资料 https://leetcode-cn.com/problems/longest-increasing-subsequence/ h

- 日理万妓/ 2022年12月04日 07:57/ 0 赞/ 208 阅读

相关最长上升子序列

Problem Description 一个数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ...,

川长思鸟来/ 2022年07月13日 01:55/ 0 赞/ 178 阅读

相关最长上升子序列

Problem Description 一个数的序列bi，当b 1 < b 2 < ... < b S的时候，我们称这个序列是上升的。对于给定的一个序列(a 1, a 2

港控/mmm°/ 2022年07月12日 02:47/ 0 赞/ 205 阅读

相关最长上升子序列

Problem Description 一个数的序列bi，当b 1 < b 2 < ... < b S的时候，我们称这个序列是上升的。对于给定的一个序列(a 1, a 2

墨蓝/ 2022年07月12日 02:47/ 0 赞/ 233 阅读

相关最长上升子序列

严格上升和非严格上升的 include <iostream> using namespace std; int main() {

柔光的暖阳◎/ 2022年06月15日 09:52/ 0 赞/ 275 阅读

相关最长上升子序列

Problem Description 一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN)

一时失言乱红尘/ 2022年05月16日 01:28/ 0 赞/ 215 阅读