dp&贪心

题解：
此题有两个问题，第一求这套系统最多能拦截多少导弹，第二个求如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

第一个问题即为求最长下降子序列，不多阐述。

对于第二个问题我是用贪心求解的。
对于每一个处在i位置的导弹，它可以和（从1到i-1位置且还没有被击落的）任一大于等于其高度的导弹共在一套装置（意思即为无需添置新的装置），在此想既然是选一个符合要求的导弹共处一套装置，则选对于之后的更有利的导弹（即为选比位置i导弹高度高的所有导弹中高度最小的那个，可以好好思考一下为何如此选）。

AC代码：

#include<iostream>
using namespace std;
const int Max = 1e5 + 5;
int lst[7], dp[7][2];//一个用来存放dp,一个用来存放贪心。至于为啥数组开这么小，因为发现这题数据是个伪1w，总共连10个导弹都没有，开个7就过了...
int g = 0;

int main()
{
    int t;
    while (cin >> t)
    {
        lst[++g] = t;
    }
    for (int i = 1; i <= g; i++)
    {
        dp[i][0] = 1;
        int f = i, f1 = 1e9 + 5;
        for (int j = 1; j < i; j++)
        {
            if (lst[i] <= lst[j]) dp[i][0] = max(dp[i][0], dp[j][0] + 1);
            if (dp[j][1] && lst[j] >= lst[i] && lst[j] < f1)
            {
                f = j;
                f1 = lst[j];
            }
        }
        dp[f][1] = 0;
        dp[i][1] = 1;
    }
    int ma = -9, sum = 0;
    for (int i = 1; i <= g; i++)
    {
        ma = max(dp[i][0], ma);
        sum += dp[i][1];
    }
    cout << ma << endl << sum;
}