C++ 拦截导弹问题

发布网友 发布时间：2022-05-03 01:45

我来回答

共5个回答

热心网友 时间：2022-06-29 05:25

求最长单调序列 简单动归（如果只求第二个的话用贪心也可以 ，不过动归可以两个一起做 而且代码更简单 ）
另外这输入数据很蛋疼 竟然没给导弹数量 所以输入要用 feof 处理一下.....
输入部分的处理应该是：
int a[21];
int n=0;
while (!feof(stdin))
{
n++;
scanf("%d",&a[n]);
}.
//n--; 输入若有回车则n-1；没有就不用这一步
求能打多少的代码是：
int max=0;
for (int q=n-1;q>=1;q--)
{
for (int p=n;p>q;p--)
if (a[q]>a[p] && t1[q]<t1[p]+1)
t1[q]=t1[p]+1;
if (max<t1[q]) max=t1[q];
}
求要多少套是把上面的代码其中一个大于号改成小于号就行了....

热心网友 时间：2022-06-29 05:26

#include<iostream>
using namespace std;
int main(){
int h[21], opt[21], count, i, j, p[21], lis, pos, bul = 0, flis, flag;
count = 0;
while(cin>>h[count++]);
count--;
flag = count;
while(flag){
for(i = 0; i < count; i++){
opt[i] = 1;
p[i] = -1;
}
lis = 0;
for(i = count - 1; i >= 0; i--){
for(j = i + 1; j < count; j++){
if(h[i] != -1 && h[j] != -1 && h[i] >= h[j] && opt[j] + 1 > opt[i]){
opt[i] = opt[j] + 1;
p[i] = j;
}
}
if(opt[i] > lis){
lis = opt[i];
pos = i;
}
}
i = pos;
while(p[i] != -1){
h[i] = -1;
i = p[i];
flag--;
}
h[i] = -1;
flag--;
if(!bul){
flis = lis;
}
bul++;
}
printf("%d\n%d\n", flis, bul);
}

热心网友 时间：2022-06-29 05:26

第一个问题用递归算法，穷举所有递减数列，找出最长的递减数列，总是容易解决的。
第二个问题似乎很难穷举所有的递减数列集合，找出集合元素最少的集合。

热心网友 时间：2022-06-29 05:27

这道题是最长非下降子序列问题，一般考虑用递归 / 动态规划求解。当然，如果数据规模不大，可以考虑穷举。

热心网友 时间：2022-06-29 05:27

为了防御敌国的导弹袭击，发展出一种导弹拦截系统