1 //
2 // Created by snnnow on 2020/4/13.
3 //
4 //每一次拦截只能是降续的导弹
5 //如果该次不能拦截成功，则拦截次数需要加一
6 //求每次最大拦截量，以及需要的拦截次数
7 //
8 //单次拦截：最长不上升序列－－dp
9 //拦截次数：（官方上叫它为＂贪心＂）就是挨个比较逆序列嘛，要是出现比所有已知逆序列最小值都大的就加次数
10 //如果有多个一样的就是
11 //
12 #include <iostream>
13 #include <string.h>
14 using namespace std;
15 int main(){
16 int a[10010]={0};//这个是用来存放输入的数的
17 int b[10010]={0};//b[i]是指a[i]这个前面连着的最长的有几个
18 int c[10010]={0};//．．
19 int i=1;
20 int maxall=0;
21 int allway = 0;//表示一共几套系统
22 while(cin>>a[i]) {
23 if (a[i] != 0) {
24 // if (i == 1) {
25 // i++;
26 // continue;
27 // } else {
28 int max = 0;
29 for (int j = 1; j <= i-1; j++) {//注意一下，j是前面的，基准数字i是刚输进去的才是后面的
30 if (a[j] >= a[i] && b[j] > max) {//有第二句条件的原因是：如果变化量a[j]有多个满足条件，就要找最大的一个了，因为b[i]是最长的
31 max = b[j];
32
33 }
34 b[i] = max + 1;//max负责记录最大量，最后给了b[i];+1是因为算上b[i]就多了一个嘛
35 if (b[i] > maxall) {
36 maxall = b[i];//用来记录所有的最大值
37 }
38
39
40 //接下来这一段是判断哪一套系统的，c[a]就是指第a套系统中的最小值
41
42 }
43 int basic = 0;
44
45 for (int k = 1; k <= allway; ++k) {//每一套系统都来试试a[i]行不行（可能一套都不行，也可能一套行或多套行）
46 if (a[i] <= c[k]) {//需要跟每一套系统的最小值比较
47 if (basic == 0) {//basic为零说明这是第一个满足条件的，那就直接归到第k组就行
48 basic = k;//还有就是先有的一套才有的多套，所以这个if大家都要进
49
50 }
51 else if (c[k] < c[basic]) {//如果有多种情况满足条件，那就找c小的，因为C大的可以满足的情况多
52 basic = k;
53 }
54 }
55
56 }
57 if (basic == 0) {//basic为０，说明没有已存在的系统，那就只能开新的了
58 allway++;
59 basic = allway;
60 }
61 c[basic] = a[i];//basic 是在为a[i]找个系统，c[basic]是a[i]存在的系统中最小的了（就是a[i])
62 i++;
63 }
64
65
66 else break;
67 }
68 cout<< maxall+1<<" "<<allway<<endl;
69 return 0;
70
71 }
刚刚debug代码，发现了几个问题
１．a,b都是从一开始的（没有影响），但是c是从０开始的
２．不上升允许相等的状态存在（＞＝）一开始漏等号，会很凉
３．注意不要重复定义变量．．还有就是变量定义的位置也很重要呀！！！（比如一开始把allway放循环里了，很让人伤心的debug)