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 zzh_2010 @ 2023-08-07 15:42:28

python本身边编译边执行，速度很慢，建议使用C/C++

by Terrible @ 2023-08-07 15:52:32

@Lantern_LZY

Python 跑不过 O(n^2)，n\leqslant 5000，所以必须优化才能过。

可以优化成 O(n\log n) 的算法，算法详见

P1020 [NOIP1999 普及组] 导弹拦截 题解做法。

下面是 Python 参考做法：

from bisect import *
n=int(input())
l=list(map(int,input().split()))
a=[l[0]]
for v in l[1:]:
  if a[-1]<v:a.append(v)
  else:a[bisect_left(a,v)]=v
print(len(a))

洛谷题目并不管 Python 能不能正常过，所以也不必非要用 Python 通过某些题。

实际上大多数 OJ 也就是至多给 Python 等开两倍的时空，有时候这依然不够。

by denghuolanshan_1004 @ 2023-08-07 15:59:17

又想起了之前只会py因此一堆简单题过不去的时刻

by denghuolanshan_1004 @ 2023-08-07 16:05:13

python啥都好，就是速度也和蟒蛇一样慢

by denghuolanshan_1004 @ 2023-08-07 16:08:39

顺便问个问题，在自动识别里面开O2然后输入python代码会怎么样

by zzh_2010 @ 2023-08-07 16:09:00

#include<cstdio>
#include<algorithm>
using namespace std;
int maxx=1,a[5005]={0},dp[5005]={0};
int main(){
    int n;scanf("%d",&n);
    fill(dp,dp+n,1);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i-1;j++){
            if(a[j]<=a[i])
            dp[i]=max(dp[j]+1,dp[i]);
        }
        if(maxx<dp[i])
        maxx=dp[i];
    }
    printf("%d",maxx);
    return 0;
}

by Terrible @ 2023-08-07 16:34:17

@denghuolanshanchu O2 在洛谷应该只限 C/C++ 。

by FENGHAOZHE1234 @ 2023-08-07 16:54:38

@denghuolanshanchu 事实上蟒蛇袭击动作只能用高速相机才能看清楚（doge

by denghuolanshan_1004 @ 2023-08-07 17:31:11

@Terrible

所以就是什么都没发生喽……

by denghuolanshan_1004 @ 2023-08-07 17:31:45

@FENGHAOZHE1234

…… 能听懂就行了