题目

https://www.luogu.com.cn/problem/P1020

第二问知道是求最大上升序列之后就很简单了,最大的问题在于为什么是求这个。试给出以下解释(严格证明需要组合数学的知识):

转化

对于给出的序列(输入数据),必定存在至少一个的最大上升子序列。任取一个最大上升子序列,其中任两个元素(导弹)必定由两套不同系统进行拦截。意味着如果最大上升子序列长度为 n,我们最少需要的系统数目必定大于或等于 n。
接下来可以用数学归纳法去解释为什么当最大上升子序列长度为 n 时最少只需要 n 套系统。
当 n = 1 时,给出的序列(输入数据)是单调递减的,显然只需要一套系统,结论成立。
假设 n = k 时结论成立。也就是只需要 k 套系统。当 n = k + 1 时,试将给出的序列一分为二分别求解,具体方法如下:枚举出所有的最大上升子序列,将每个最大上升子序列的尾元素分别取出。如果某个数是多个最大上升子序列的尾元素则只取出一次。将取出的数按照原本的先后顺序排列生成一个新的序列(假设叫序列 1)。未取出的数也按照原来的先后顺序排列形成另一个新的序列(假设叫序列 2)。
此时序列 2 的最大上升子序列长度必定为 k,那么根据前面的假设,需要 k 套系统。而序列 1 是单调递减的(可用反证法证明),由已知需要 1 套系统。所以加起来就是 k + 1 套系统。因为 k + 1 套系统可以拦截所有导弹,而由已知,需要配备的系统数需要大于等于 k + 1,所以 n = k + 1 时结论也成立。

100 分代码(n 方算法)

#include <bits/stdc++.h>
using namespace std;

int a[100005], num = 1;
int ans[100005];
int main()
{
    while (cin >> a[num])
        num++;
    num--;
    a[0] = 50001;
    int maxans = 0;
    for (int i = 1; i <= num; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (a[i] <= a[j])
            {
                // cout << ans[i] << " " << ans[j] + 1 << endl;
                ans[i] = max(ans[i], ans[j] + 1);
            }
        }
        // cout << ans[i] << endl;
        if (ans[i] > maxans)
            maxans = ans[i];
    }
    cout << maxans << endl;

    memset(ans,0,sizeof(ans));
    maxans = 0;
    a[0] = 0;
    for (int i = 1; i <= num; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (a[i] > a[j])
            {
                // cout << ans[i] << " " << ans[j] + 1 << endl;
                ans[i] = max(ans[i], ans[j] + 1);
            }
        }
        // cout << ans[i] << endl;
        if (ans[i] > maxans)
            maxans = ans[i];
    }
    cout << maxans << endl;
    return 0;
}

200 分代码(nlogn 算法)

#include <bits/stdc++.h>
using namespace std;
int a[100010], b[100010];
int num = 0, p, ans;

bool cmp(int a, int b)
{
    return a > b;
}

int main()
{
    while (cin >> a[anum])
        num++;

    ans = 1;
    b[0] = a[0];
    for (int i = 1; i < num; i++)
    {
        if (a[i] <= b[ans - 1]){
            b[ans] = a[i];
            ans++;
        }
        else
        {
            p = upper_bound(b, b + ans, a[i], cmp) - b;
            b[p] = a[i];
        }
    }
    // for (int i = 0; i < ans; i++)
    // {
    //     cout << b[i] << " ";
    // }
    // cout << endl;
    cout << ans << endl;

    ans = 1;
    b[0] = a[0];
    for (int i = 1; i < num; i++)
    {
        if (a[i] > b[ans - 1]){
            b[ans] = a[i];
            ans++;
        }
        else
        {
            p = lower_bound(b, b + ans, a[i]) - b;
            b[p] = a[i];
        }
    }
    // for (int i = 0; i < ans; i++)
    // {
    //     cout << b[i] << " ";
    // }
    // cout << endl;
    cout << ans << endl;
    return 0;
}
最后修改:2019 年 11 月 29 日 08 : 26 PM
如果觉得我的文章对你有用,请随意赞赏