最长不下降代码dp

我看以前写过一个最长不下降，但是感觉可能没有那么好理解emmmm

下面这个是从正序寻找的emmmm

先来一个ＷＡ代码，我给写了ＷＡ的具体行数，看看其他行其实可以看出它的思路

第二个代码是ＡＣ的

 1 #include <iostream>
 2 #include <string>
 3 #include <string.h>
 4 #include <vector>
 5 using namespace std;
 6 long MAX=1010;
 7 int a[1000];
 8 int maxa[1000];
 9 int pos[1000];
10 int main() {
11     int N;
12     cin >> N;
13     for (int i = 1; i <= N; ++i) {
14         cin >> a[i];
15         maxa[i] = 1;
16     }
17     int maxfinal=0;
18     int final_pos=0;
19     for (int k = 2; k <= N; ++k) {
20         for (int i = k-1; i >=1; --i) {
21             if (a[k] > a[i]) {
22                 maxa[k] = max(maxa[k], maxa[i] + 1);
23                 pos[k]=i;//WA典范，因为maxa可能没有取maxa[i]的值，但是pos 一直在改变
24                 if (maxa[k] > maxfinal) {
25                     maxfinal = maxa[k];
26                     final_pos=k;
27                 }
28 
29             }
30         }
31     }
32     cout<<maxfinal<<endl;
33     for (int l = 1; l < 5; ++l) {
34         cout<<pos[l]<<endl;
35 
36     }
37     for (int j = final_pos;  ; ) {
38         if(a[j]==0)
39             break;
40         cout<<a[j]<<" ";
41         j=pos[j];
42 
43 
44     }
45 
46 
47 
48 }

没错就是max(,)的下一行，但是如果只需要输出长度的话就把这行给注释掉就行了

 1 #include <iostream>
 2 #include <string>
 3 #include <string.h>
 4 #include <vector>
 5 using namespace std;
 6 long MAX=1010;
 7 int a[1000];
 8 int maxa[1000];
 9 int pos[1000];
10 int main() {
11     int N;
12     cin >> N;
13     for (int i = 1; i <= N; ++i) {
14         cin >> a[i];
15         maxa[i] = 1;
16     }
17     int maxfinal=0;
18     int final_pos=0;
19     for (int k = 2; k <= N; ++k) {
20         for (int i = k-1; i >=1; --i) {
21             int data;
22             if (a[k] > a[i]) {
23                 if(maxa[k]<maxa[i] + 1) {
24                     maxa[k] = maxa[i] + 1;
25                     pos[k] = i;
26                     if (maxa[k] > maxfinal) {
27                         maxfinal = maxa[k];
28                         final_pos = k;
29                     }
30                 }
31 
32             }
33         }
34     }
35     cout<<maxfinal<<endl;
36     for (int j = final_pos;  ; ) {
37         if(a[j]==0)
38             break;
39         cout<<a[j]<<" ";
40         j=pos[j];
41 
42 
43     }
44 
45 
46 
47 }

这个是输出序列的，那个存数方式还算很常用

还有就是，一维数组比二维要快？我一会儿写一篇来检测一下哈