这道题难就难在问题二的解决,可以直接看我的问题二解决代码
以下是问题二的可视化模拟:
/*
* @Author: YMYS
* @Date: 2024-12-17 08:44:40
* @LastEditTime: 2024-12-23 15:18:59
* @FilePath: \VScode-C&C++-Coding\Acwing\算法提高课\1.动态规划\2.最长上升子序列模型\6.拦截导弹.cpp
* @URL:https://www.acwing.com/problem/content/1012/
* @Description: 1010. 拦截导弹
*
* 问题一:最长不下降子序列
*
* 问题二:贪心。
* 最少用多少个非下降子序列把数据覆盖掉的方案数 == 最长上升子序列的方案数
*
*
* PS:送上一篇非常好的题解:https://www.acwing.com/solution/content/239646/
*
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1010;
int n;//数组长度
int w[N],f[N],g[N];
signed main()
{
#ifdef ABC
freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
#endif
while (cin>>w[n+1]) n++;//整个数组从1开始存的,1~n
//第一问
//求解最长不上升子序列
for(int i=n;i>=1;i--){
f[i] = 1;
for(int j =n;j>i;j--){
if(w[i] >= w[j]) {
f[i] = max(f[i], f[j]+1);
}
}
}
int tmp = 1;
for(int i=1;i<=n;i++){
tmp = max(tmp, f[i]);
}
cout << tmp << endl;
//第二问
//这一问我们采用贪心去做
//g[i]表示第i个子序列的末尾的值,也就是该子序列的最小高度
int cnt = 0;
for(int i=1;i<=n;i++){
int k = 0;
while(k<cnt && w[i] > g[k]) k++;
if(k >= cnt){//如果都把当前序列数量搜完了还没有任何一个序列能放下i 我们就新开一个序列来存i
g[cnt++] = w[i];//刚开始的时候cnt=0并没有存值,所以我们这里用的是cnt++而不是++cnt
}else{//这里是w[i]<=g[k]的,就是我们发现我们遍历到的一个w[i]可以插入到已有的不上升子序列中,因此我们就不用再新增子序列了
g[k] = w[i];//更新子序列的值,保持为最小
}
}
cout<<cnt<<endl;
return 0;
}