第二题 Python版 import sys if __name__ == "__main__": def lagr(l,num): dp = [1]*l for i in range(l): for j in range(i): if num[j] < num[i] and dp[i]<dp[j]+1: dp[i] = dp[j] +1 s = max(dp) return l-s def small(l,num): dp = [1]*l for i in range(l): for j in range(i): if num[j] > num[i] and dp[i]<dp[j]+1: dp[i] = dp[j] +1 s = max(dp) return l-s n = int(sys.stdin.readline().strip()) for i in range(n): l = n = int(sys.stdin.readline().strip()) line = sys.stdin.readline().strip() nums = list(map(int, line.split())) ans = min(lagr(l,nums),small(l,nums)) print(ans)