[数据结构与算法] 信息学奥赛一本通 1289：拦截导弹

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 信息学奥赛一本通 1289：拦截导弹 -> 正文阅读

[数据结构与算法]信息学奥赛一本通 1289：拦截导弹

【题目链接】

ybt 1289：拦截导弹
原题有两个问，本题为第1问

【题目考点】

1. 动态规划：线性动规

求最长下降子序列

【解题思路】

求最长下降子序列
状态定义：dp[i]表示以i为结尾的最长下降子序列的长度。
状态转移方程：
分割集合：以第i元素为结尾的下降子序列构成的集合。

子集1：对所有满足j < i的j，如果a[i]<a[j]，则以第j元素为结尾的下降子序列加上第i元素，形成新的下降子序列。下降子序列的长度dp[i] = dp[j]+1。
子集2：否则，只有一个第i元素构成下降子序列。dp[i] = 1。
以上取到的各值求最大值

最后求dp数组的最大值，即为最长下降子序列的长度。

【题解代码】

解法1：线性动规

#include <bits/stdc++.h>
using namespace std;
#define N 20
int n, dp[N], a[N], ans;//dp[i]:以i为结尾的最长下降子序列的长度 
int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    for(int i = 1; i <= n; ++i)
    {
        dp[i] = 1;
        for(int j = 1; j < i; ++j)
            if(a[j] > a[i])
                dp[i] = max(dp[i], dp[j] + 1);
        ans = max(ans, dp[i]);
    }
    cout << ans;
    return 0;
}