https://vjudge.net/problem/HDU-4604 给定一排数和一个 双头队列。 可以往头插还可以往后插的，问你最大得到的 非递减队列的长度。 经过分析，枚举每个点作为开头的 最大非严格递增和 最大非严格递减子序列，然后相加 减去他们 中重叠的数。 重叠的数是这样计算的。分别计算一个数在 两个数列中的数量，然后取最大的那一个
前天才看懂代码的意思，被一个地方卡了。 首先, a=upper_bound(a,a+n,x)-a; b=lower_bound(a,a+n,x)-a; 1 a-b+2 和 upper_bound()-lower_bound()其实是一样的。。 只是写法不同，都是计算那个x在a[]中的数量。。 2 别人一句话就给我说明白了。lis本来是求的dp[]是以i为末尾的长度。如果反响求，并且递增改成递减，就可以求以头为长度的了。 并且要 注意 差别，递增和非递降有点差别， 如果用的是a，即每次插入都是在第一个大于他的数，那就是非递降啊（相同的数得以保存，数组中假设有一个 1 2 3 ，那么再插入一个3，还是可以插在最后面的，哈哈两个3 了如果这样。） 但是如果是用b呢，那么就还是得到 12 3 ，还是一个3，、 就这点不一样。 4 另外我感觉还是应该锻炼自己的思考能力，多思考基本的dp结构。 这种题可以加强对lis的理解。 6 我第一次吧name初始化为1，然后求最大的也过了。突然我发现。 两个数列中 同一个数的存在个数肯定是相同的。 求最大的和最小的都是一样的。除非一个 正常递增，一个非严格递减，然后出现不同的情况，不过这种情况用本题的代码也可以算。 如果求最小的就初始化为0x3f3fl
第一次反转，求的是以一个点为首的下降子序列（但是位置不是以前的位置，即第一个数其实是原数组中倒数第一个数的） 在反转的基础上又进行了 取负值，求的才是以这个数的上升，不过也是相反的位置，和上一个一个，故进行加减不会造成损失
#include <bits/stdc++.h> using namespace std; /*先求一个 递降（非标准递降，就是不递升） 然后再求一次递升，（非标准递升，就是不递降） 本来lis计算的是为最后的数，倒着计算就是为头的数。 该球递降的求递升，该求递升的求递降 二者相反，但由于这道题二者都需要计算，所以就不用了 qwq */ const int maxn=100006; int a[maxn]; int num[maxn]; int n; int solve(int dp[]) { vector<int>q;//设置一个队列来储存这个序列. for(int i=0;i<n;i++) { int a1=upper_bound(q.begin(),q.end(),a[i])-q.begin();//用来计算第一个比他大的 int b1=lower_bound(q.begin(),q.end(),a[i])-q.begin(); if(a1==q.size()) { q.push_back(a[i]); dp[i]=q.size(); } else { q[a1]=a[i];//把第一个大于的数给换掉 dp[i]=a1+1; } num[i]=min(num[i],a1-b1+1);//或者初始为1，求最大 } return 0; } int main() { std::ios::sync_with_stdio(false); int dp1[maxn]; int dp2[maxn]; int t; cin>>t; while(t--) { memset(dp1,0,sizeof(dp1)); memset(dp2,0,sizeof(dp2)); memset(num,0,sizeof(num)); memset(a,0,sizeof(a)); scanf("%d",&n); for(int i=0;i<n;i++) num[i]=0x3f3f3f3f;//为什么要设置成0呢，因为最少一个数也是0啊。。 for(int i=0;i<n;i++) scanf("%d",&a[i]); for(int i=0;i<n;i++) reverse(a,a+n); solve(dp1); for(int i=0;i<n;i++) a[i]=-a[i]; solve(dp2); int all=0; for(int i=0;i<n;i++) all=max(all,dp1[i]+dp2[i]-num[i]); printf("%d\n",all); } return 0; }