LTS（最长不下降序列）&&之前的跳跃问题
帮师姐做今日头条笔试
我的一个错误的思路：
假设输入数据是10个数据：“10 3 7 5 1 10 3 7 5 1“”
一、始终维护一个最长不下降序列组合集合G，顺序每过一个数据，都更新保存当前的组合集合。
二、G中最长的vector为A1，第二长的为A2，以此类推。
三、具体的策略为：
top指的是A的最后添加的数（末尾的数），down是开头的数
（1）在A[]中添加新成员：新来的数比任何一个top大或相等，更新那个被改变的top。
（2）建立新vector：新来的数据比所有down都小，且去除所有长度为1的vector。
（3）替换A的：新来的数据比所有down都小，且去除所有长度为1的vector。
| A1 | A2 | 备注 | |
| 10 | 10 | ||
| 3 | 3 | 3比10小，而且“3”和“10”长度都为1，所以保存3 | |
| 7 | 3--7 | ||
| 5 | 3--5 | 5比7小，而且“3-5”和“3-7”长度都为2 | |
| 10 | 3--5--10 | ||
| 3 | 3--5--10 | 3并不比down1小 | |
| 7 | 3--5--7 | 7比3大，所以不更新A2，7比10小，所以更新A1 | |
| 5 | 3--5--5 | 5比3大，所以不更新A2，5比7小，所以更新A1 | |
| 10 | 3--5--5--10 | 3并不比down1（3）小 | |
| 3 | 3--5--5--10 | 3并不比down1（3）小 | |
| 7 | 3--5--5--10 | 3并不比down1（3）小 | |
| 5 | 3--5--5--10 | 3并不比down1（3）小 |
| A1 | A2 | 备注 | |
| 10 | 10 | ||
| 3 | 3 | ||
| 7 | 3--7 | ||
| 5 | 3--5 | ||
| 1 | 3--5 | 1 | 1比3小，所以维护新的A2 |
| 10 | |||
| 3 | |||
| 7 | |||
| 5 | |||
| 1 |
想到这里的时候想出问题了，如果我按照顺序这样删的话，遇到3 6 7 8 9 5 5 5 5 5 5 我就会出问题，不是3 6 7 8 9 而是3 5 5 5 5 5 5反正我可能会需要维护多个vector。应该用多叉树的方法可以实现顺序计算量，但是树本身的计算可能会费功夫
举例，可以用来玩：
1 7 4 0 9 4 8 8 2 4
5 5 1 7 1 1 5 2 7 6 （8个）
1 7 4 0 9 4 8 8 2 4
5 5 1 7 1 1 5 2 7 6
1 4 2 3 2 2 1 6 8 5
7 6 1 8 9 2 7 9 5 4
3 1 2 3 3 4 1 1 3 8（14次） （1-1-1-1-1-2-2-2-2-2-3-3-3-8）
但是宇宙条的这道题奇怪在它是规律的所以应该要用上规律，所以规律我没用上挺可惜的。（我能想到用到多叉树当中就是因为每年的规律所以不用建立新的树了，就在老树上进行判断）
具体的原则是：
（1）基本原则：根是小的，树叶是大的，依次排序。
（2）新的结点，只在有意义的时候才会放入树当中。
所谓有意义是指：2.1对比目前维护的树的每个结点的大小，比当前层的所有数都要小，才放入这个层当中，否则抛弃。
2.2 层数更深的有意义
（3）第2点的变体：如果最新的数比当前维护的树的根都要小，那就开始维护新的树。但是所有树的层是在一起比较的。
（4）当树的某一层到达了跟当前层相同的高度时，比较两个层的叶子结点哪个小一点，保留小的，大的那个一直删到有意义的结点为止（有意义的那一个不删）
找的一个可以用的代码：
#include<iostream>
using namespace std;
int main()
{
int a[10000], g[10000];
/*int i, j, n, max;
cin >> n;// scanf("%d", &n);
for (i = 1; i <= n; i++)
cin >> a[i];// scanf("%d", &a);*/
int i, j, n, t, max;
cin >> n >> t;
for (i = 1; i <= n; i++)
{
cin >> a[i];
}
for (i = n + 1, j = 1; i <= (n*t); i++)
{
a[i] = a[j];
j++;
if (j == n + 1)
{
j = 1;
}
}
//动规边界，初始化
g[1] = 1;
//动规开始
for (i = 2; i <= n*t; i++)
{
g[i] = 1;//初值，这里很重要。。。。。位置不要写错，要在for(j)循环的外面
//每次找i前面所有的数，所以是1到i-1
for (j = 1; j <= i - 1; j++)
{
//枚举前面的每个数是不是比当前这个数小, 注意这里是不下降子序列，所以是小于等于
if (a[j] <= a[i])
{
if (g[i] < g[j] + 1)
g[i] = g[j] + 1;
}
}
}
//找g函数中的最大值
max = 0;
for (i = 1; i <= n*t; i++)
{
if (max < g[i])
max = g[i];
}
cout<<max;// printf("%d", max);
return 0;
}
将该问题转换成了求解g数组的最大值，g数组保存的是：
g[i]保存了：a[0]到a[i]的最长不下降序列的序列长度，计算量是O（N^2）。
二、跳跃问题
题目：
给定非负整数数组，初始时在数组起始位置放置一机器人，数组的每个元素表示在当前位置机器人一步最大能够跳跃的数目。它的目的是用最少的步数到达数组末端。
例如：
给定数组A=[2,3,1,1,2]，最少跳步数目为2，对应的跳法是2->3->2，数组位置变化为0->1->4。
[2,3,1,1,2,4,1,1,6,1,7]，所需步数为5。
代码：
网上某位大哥的（想法跟我一样，我觉得它整体写的没我清楚嘻嘻嘻）
#include<iostream>
using namespace std;
int jump(int A[],int n){
if(n==1)
return 0;
int step=0;
int i=0,j=0;
int k,j2;
while(j<n){
step++;
j2=j;
for(k=i;k<=j;k++){
j2=max(j2,k+A[k]);
if(j2>=n-1)
return step;
}
i=j+1;
j=j2;
if(j<i)
return -1;
}
return step;
}
int main(){
int A[]={2,3,1,1,2,4,1,1,6,1,7};
int n=sizeof(A)/sizeof(A[0]);
cout << jump(A,n) <<endl;
return 0;
}我的思路很简单：[2,3,1,1,2,4,1,1,6,1,7] 首先在2,2能跳到3和1，跳到3最大贡献是1+3=4；跳到1最大贡献是2+1=3；
那肯定去3啊，到了3之后，3能去1 1 2，分别是1+1=2；2+1=3:3+2=5，那肯定去5啊
int lalal(int* a,int index,int num)
{
int temp = 0;
int max_temp = 0;
int save_index = 0;
for(int i = 1; i <=num; i++)
{
temp = i + a[index + i];
if (max_temp < temp)
{
max_temp = temp;
save_index = i;
}
}
return index+save_index;
}
int main()
{
int a[11] = { 2, 3, 1, 1, 2, 4, 1, 1, 6, 1, 7 };
int num =11;
int sum = 0;
int time = 0;
for (int index = 0; index < num;)//其实这个也可以分装成一个函数直接调用
{
int b = lalal(a, index, a[index]);
sum += a[b];
index = b;
cout << b << endl;
time++;
if (sum >= num-1)
{
if (index != num - 1)
{
cout << num-1<< endl;
time++;
}
break;
}
}
cout << "time:" << time << endl;
}