文章目录
- 题目描述
- 思路分析
- 实现源码
- 分析总结
题目描述
思路分析
- 目前是有一个笨办法,就是创建链表记录每一个最长下降子序列所对应的节点的链接,然后逐个记录所有结点的访问情况,直接所有节点都被访问过。
- 这个方法不是很好,因为需要计算很多次,会超时,这里用了贪心的方法来证明,虽然不是最优子序列,但是数量是一致的。
实现源码
#include <iostream>
#include <algorithm>
#include <sstream>using namespace std;const int K = 110;
const int N = 110;
const int H = 12000;
int h[H];
int Up[N];
int Down[N];
struct Node {int idx;Node *next;
};
bool DownAcess[N];
Node DownRecord[N]; // 记录下降节点的序列int main() {int n = 1;string line;getline(cin,line);stringstream ss(line);while(ss>>h[n]) n++;n --;int times = 0;bool endFlag = true ;
// while(endFlag){
// endFlag = false;
// times ++;
// int maxIdx = 1;
// int maxNum = 0;// 计算最长上升子序列int res = 0;for (int i = n; i >= 1; -- i) {Down[i] = 1;DownRecord[i].idx = i;// 右侧最长上升子序列for (int k = n; k > i ; --k) {if (h[k] <= h[i]){Down[i] = max(Down[i], Down[k] + 1);if (Down[i] < Down[k] + 1)DownRecord[i].next = &DownRecord[k];}}res = max(res, Down[i]);}cout<<res<<endl;
//
// for (int i = 1; i <= n; ++i) {
// if (maxNum < Down[i]) {
// maxIdx = i;
// }
// }
//
// Node *temp = &DownRecord[maxIdx];
// while(temp != NULL){
// DownAcess[temp->idx] = true;
// }
//
// for (int i = 1; i <= n; ++i) {
// if (DownAcess[i] == false) endFlag = true;
// }// }
// cout<<times<<endl;return 0;
}
// 正解
//#include<iostream>
//#include<algorithm>
//using namespace std;
//
//const int N = 1005;
//int n;
//int q[N];
//int f[N],g[N]
//
//int main()
//{
// while(cin>> q[n]) n ++;
// int res = 0;
// for (int i = 0; i < n; ++i) {
// for (int j = 0; j < i; ++j) {
// if (q[j] <= q[i])
// f[i] = max(f[i],f[j] + 1);
// }
// res = max(res,f[i]);
// }
// cout<<res<<endl;
//
// int cnt = 0;
// for(int i = 0;i < n;i ++){
// int k = 0; // 维护的索引的序列
// while(k < cnt && g[k] < q[i]) k ++; // 遍历的每一个维护的最大的序列值
// g[k] = q[i];
// if(k >= cnt) cnt ++;
//
// }
//}
分析总结
- 这里的证明看的不是很懂,但是用样例推过了,确实是正确的。使用贪心求最少的子序列数量,和两次最优子序列是相同的。
- 但是如果确实想不起来,确实可以使用这个方法进行实验。