题解 | 拦截导弹

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 30;
int s[N];
int dp[N];

int main() {
    int k;
    while (cin >> k) { 
        for(int i=1;i<=k;i++)cin>>s[i],dp[i]=0;
        
        dp[1]=1;

        for(int i=2;i<=k;i++){
            bool flag=true;      //是否不存在S[j]>=S[i] 初始状态是true；
            for(int j=1;j<i;j++){
                if(s[j]>=s[i]) dp[i]=max(dp[j]+1,dp[i]),flag=false;
            }
            if(flag) dp[i]=1;
        }
        sort(dp+1, dp+k+1);
        cout<<dp[k]<<endl;
    }
}
// 64 位输出请用 printf("%lld")

最长递增子序列（LIS）是动态规划中最经典的问题之一；

【问题描述】：

​ 在一个已知序列{A1, A2, …, An} 中，取出若干元素（不必连续）组成一个新的子序列 {Ax ,... , Ay}，子序列中的各个数之间依旧保持原序列中的先后顺序。若对子序列中的任意下标 x < y 有 Ax < Ay，则称该子序列为原序列的一个递增子序列。最长递增子序列问题就是求给定序列的所有递增子序列中最长的那个子序列长度。

【动态规划法-算法思路】：其时间复杂度为 O()。

1. 首先设置一个数组 dp[]，令 dp[i]表示以 A[i]作为末尾的最长递增子序列的长度。于是通过该数组，最长递增子序列的长度便是数组 dp 中的最大值。由于 dp[i]是以 A[i]作为末尾的最长递增子序列的长度，因此只有两种情况：
1. ①A[i]之前的元素都比 A[i]大：即最长递增子序列只有 A[i]本身，即 dp[i] = 1。
2. ②A[i]之前存在元素 A[j]比 A[i]小：此时只需将 A[i]添加到以 A[j]作为末尾的最长递增子序列，便能构成一个dp[i]的递增子序列。由dp的定义知， dp[j]是以 A[j]作为末尾的最长递增子序列的长度，因此这个以A[i]结尾的子序列的长度 dp[i] = dp[j] + 1；
2. 只需将 i 之前的元素逐一遍历，便可获得以 A[i]作为末尾的最长递增子序列的长度 dp[i]。
3. 从这两种情况可以得到状态转移方程： dp[i] = max{dp[i],dp[j] + 1 | j<i &&} ;