P1020

P1020 [NOIP1999 普及组] 导弹拦截 思考 这题很显然是一道DP题，第一问就是求该序列的最长不下降子序列. 先说最长不下降子序列的$O(n^2)$的做法. 用$dp[k]$表示第$k$位时最大的最长不下降子序列的长度， 那么我们很容易可以得到： 当$dp[i]<dp[j]$且$i>j$ ......