国产做爰全免费的视频网站,wordpress pdf 打印,网站建设深圳龙华,网站开发会遇到哪些问题文章目录 题目描述思路分析实现源码分析总结 题目描述 思路分析
目前是有一个笨办法#xff0c;就是创建链表记录每一个最长下降子序列所对应的节点的链接#xff0c;然后逐个记录所有结点的访问情况#xff0c;直接所有节点都被访问过。这个方法不是很好#xff0c;因为需… 文章目录 题目描述思路分析实现源码分析总结 题目描述 思路分析
目前是有一个笨办法就是创建链表记录每一个最长下降子序列所对应的节点的链接然后逐个记录所有结点的访问情况直接所有节点都被访问过。这个方法不是很好因为需要计算很多次会超时这里用了贪心的方法来证明虽然不是最优子序列但是数量是一致的。
实现源码
#include iostream
#include algorithm
#include sstreamusing 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(ssh[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]);}coutresendl;
//
// 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;
// }// }
// couttimesendl;return 0;
}
// 正解
//#includeiostream
//#includealgorithm
//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]);
// }
// coutresendl;
//
// 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 ;
//
// }
//}分析总结
这里的证明看的不是很懂但是用样例推过了确实是正确的。使用贪心求最少的子序列数量和两次最优子序列是相同的。但是如果确实想不起来确实可以使用这个方法进行实验。
