浙江省建设厅网站地址,足球比分网站建设,网络销售推广公司,微官网和手机网站一样吗注意事项#xff1a; 本题为线性dp—最长上升子序列的长度的扩展题#xff0c;这里只讲贪心思路#xff0c;dp去这个看。
题目#xff1a; 某国为了防御敌国的导弹袭击#xff0c;发展出一种导弹拦截系统。 但是这种导弹拦截系统有一个缺陷#xff1a;虽然它…注意事项 本题为线性dp—最长上升子序列的长度的扩展题这里只讲贪心思路dp去这个看。
题目 某国为了防御敌国的导弹袭击发展出一种导弹拦截系统。 但是这种导弹拦截系统有一个缺陷虽然它的第一发炮弹能够到达任意的高度但是以后每一发炮弹都不能高于前一发的高度。 某天雷达捕捉到敌国的导弹来袭。 由于该系统还在试用阶段所以只有一套系统因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度雷达给出的高度数据是不大于30000的正整数导弹数不超过1000计算这套系统最多能拦截多少导弹如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式 共一行输入导弹依次飞来的高度。
输出格式 第一行包含一个整数表示最多能拦截的导弹数。 第二行包含一个整数表示要拦截所有导弹最少要配备的系统数。
数据范围 雷达给出的高度数据是不大于30000的正整数导弹数不超过1000。
输入:
389 207 155 300 299 170 158 65输出
6
2#include cmath
#include cstring
#include iostream
#include algorithm
using namespace std;const int N 1010;
int n;
int w[N], f[N], g[N];//最长下降子序列模板
int lis() {int res 0;for (int i 0; in; i) {f[i] 1;for (int j 0; ji; j) {if (w[j] w[i]) f[i] max(f[i], f[j] 1); //这里注意是因为题目中说的是每一发炮弹都不能高于前一发的高度。}res max(res, f[i]);}return res;
}int main()
{//读入int x;while (cin x) w[n] x;//dp最长下降子序列模板cout lis() endl;//贪心求出最多需要多少个策略, res表示链的个数。//思路是每次从第一个链开始找到比当前值大且在是所有链尾中最小的那个将其替换也就是单调下降队列的思路。//如何证明这样写就一定保证w[i]会加在比当前导弹大且在所有链尾中最小的后面//假设有两条链, g[1]...x1, g[2]...x2, 那么此时x1必定小于x2, 因为如果x2x1, 那么g[1]应该...x1x2。int res 0;for (int i 0; in; i) {int k 0;while (k res g[k] w[i]) k;g[k] w[i];if (k res) res;}cout res endl;return 0;
}思路 dp思路和最长上升子序列长度一样不多讲。 这里着重说一下第二部分的贪心的思路。
首先猜测一下性质根据题目所说需要求出几套系统能够拦截所有导弹。
那也就是找到用几个下降子序列能够完全覆盖整个数列。 可以将每个下降子序列看作一个链完全单调下降每遇到一个新的导弹尝试将其放到合适的下降子序列的末尾那怎么算是合适呢
答案是找到当前所有链尾中比新导弹高度更高且是所有链尾中最小的那个。
怎么证明这个贪心思路是正确的调整法 首先贪心答案(A), 最优解(B), 证明A B, B A也就是A B A B: 因为贪心是一种解所以符合A B. B A: 当条件成立而A ! B, 说明A和B肯定有某个链是不同的也就是在链的某个点c产生了分歧 贪心a1链…c… 最优a2链…c… 而贪心的策略是将每个数放到比新导弹大且是链尾中最小的那个后面那就说明最优解的前一个量是要比贪心解的前一个量要大的那么就可以将贪心解的c替换到最优解的c的位置而不影响链的数量即证明了A B
声明 算法思路来源为y总详细请见https://www.acwing.com/ 本文仅用作学习记录和交流
