题解 | 拦截导弹

Q1：很明确就是最长递减子序列的长度

Q2：根据Dilworth定理:最少的下降序列个数就等于整个序列最长上升子序列的长度

n=eval(input())
heights=list(map(int,input().split()))
dp=[1]*n # Q1:最长递减子序列
dp2=[1]*n # Dilworth定理:最少的下降序列个数就等于整个序列最长上升子序列的长度
for i in range(1,n):
    for j in range(0,i):
        if heights[i]<=heights[j]:
            dp[i]=max(dp[j]+1,dp[i])
        else:
            dp2[i]=max(dp2[j]+1,dp2[i])
print(max(dp))
print(max(dp2))