pyhon3TLE求助

Lantern_LZY @ 2023-08-07 15:23:25

nums=list(map(int,input().split()))
def long(nums):
    if not nums:
        return 0
    dp=[1]*len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[i]>nums[j]:
                dp[i]=max(dp[i],dp[j]+1)
    return dp

dp=long(nums)
m=max(dp)
print(m)
#5 TLE

by FENGHAOZHE1234 @ 2023-08-07 18:18:46

emmm......雀食。 不过在除了做题以外的方面python确实特别好用。本人就是先学的python，大概有2年左右了，4级水平（C艹差不多）

by Lantern_LZY @ 2023-08-09 14:58:01

@zzh_2010 正在学习c++，但能力不足，写不了算法题

谢谢建议，已关

by Lantern_LZY @ 2023-08-09 15:04:28

@Terrible 谢谢大佬的回答，已关。

但不懂怎么优化的，能讲讲么

by Lantern_LZY @ 2023-08-09 15:10:16

@FENGHAOZHE1234 @denghuolanshanchu

谢谢回复，这是蒟蒻的最高楼

已关

by Terrible @ 2023-08-09 15:53:37

@Lantern_LZY

详见 P1020 [NOIP1999 普及组] 导弹拦截 的题解做法，本题要求只是上述题要求的一部分。

by Terrible @ 2023-08-09 15:55:33

或许你可以在算法能力提升之后再来用 O(n\log n) 时间复杂度的算法来写，或者在学完 C/C++ 等编译语言之后再来尝试。

by Lantern_LZY @ 2024-05-21 21:04:02

@Terrible 大佬，我c++学完dp了！这道题我用c++做出来了！

#include<bits/stdc++.h>

using namespace std;

int n,maxi=1;
int main(){
    cin>>n;
    vector<int> arr(n);
    vector<int> dp(n,1);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            if(arr[j]<arr[i]){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
        maxi=max(dp[i],maxi);
    }

    cout<<maxi;
}