第一问没什么说的，跟DP9 一样，就是改成了下降序列。 第二问求个数，由于没思路，查题解查到了一个Dilworth定理 偏序集能划分成的最少的全序集个数等于最大反链的元素个数。 查到的一个比较好的博客 对本题，第二问就是求该序列“严格上升子序列最大长度”，这个数就等于所求的 下降序列个数 #include<iostream> #include<cstring> /* 拦截导弹 最长下降子序列 以及 子序列个数 */ using namespace std; const int MAXN = 1000+1; int arr[MAXN]; int dp[MAXN]; int...

DP问题五步走：  dp数组的含义以及下标的含义 递推公式 如何初始化 遍历顺序 打印数组  本题对前四个问题有着非常好的示范效果。 题目分析在代码里解释的应该比较详细了，不再赘述。 吐槽一下测试用例有六次方，题目里说了到五次方。 第一篇牛客题解，溜了溜了 #include<iostream> #include<cstring> /* 描述 给定一个整数数组 cost ，其中 cost[i] 是从楼梯第i 个台阶向上爬需要支付的费用，下标从0开始。 一旦你支付此费用，即可选择向上爬一个或者两个台阶。 */ using namespace std; const int M...