- //
- // Created by snnnow on 2020/4/13.
- //
- // 这是 dp 问题的基础题
- //
- // 最长不下降
- //(导弹拦截是其例题)
- // 那这篇文章是讲啥呢,
- // 主要是吧, 这个题是用了二维数组,
- // 而导弹当时是用了三个一维数组
- // 其实本质上是一样的
- //(有本事干结构体啊! QAQ[手动狗头])
- // 不多说了, ans[i][1]是原数
- //ans[i][2]是该项的最长
- //ans[i][3]是指向下一个(下一个值的位置)
- // 开始咯!
- #include <iostream>
- using namespace std;
- int main(){
- int ans[10010][10];// 虽然第二维我们只要三个数, 但是还是最好开大一点
- int n;
- cin>>n;
- for (int i = 1; i <= n ; ++i) {
- cin>>ans[i][1];
- ans[i][2]=1;
- ans[i][3]=0;
- }
- for (int j = n-1; j>= 1; --j) {
- int k=0;// 注意一个问题, k 和 p 是每次 i 需要更新的, 所以一定放在这个循环这里
- int p=0;
- for (int i = j+1; i <= n ; ++i) {
- if(ans[j][1]>= ans[i][1] && ans[j][2]> k){//k 记录的就是所有的 ans[j][2]中最大的
- k = ans[j][2];
- p = j;
- }
- if(k>0){
- ans[i][3] = p;//p 就是个"指针",ans[j][3]存放的就是个位置
- ans[i][2] = k+1;
- }
- }
- }
- // 挨个比较一下 ans[i][2]就可以找到最大的, 注意要找个变量标记出来啊
- int mark=1;
- for(int i=1;i <= n;i++){
- if(ans[i][2]>= ans[mark][2]){
- mark = i;// 这里不是排序, 不需要双重循环, 只需要找一个东西一直比较着就行
- }
- }
- cout << ans[mark][2]<<endl;
- while(mark!=0){
- cout<<" "<<ans[mark][1];
- mark = ans[mark][3];
- }
- return 0;
- }
这次, 把第一个逆序循环 --j 写成了 ++j..直接炸了
然后把 k 的定义写错了位置 (k 是跟随每一个 ans[i] 更新的)
太傻了, 小白还要继续加油!
来源: http://www.bubuko.com/infodetail-3505385.html