原题链接经过若干组数据发现贪心可行性后试图证明请移步code#include<bits/stdc++.h>usingnamespacestd;intmain(){intt;cin>>t;while(t--){intn,ans=0;cin>>n;intx=2e9,y=3e9;for(inti=1;i<=n;i++)

我们只需要记录每个数结尾的数是多少（有点最长上升子序列的味道）这种子序列的题目很多都是这样的，因为不需要连续很多时候我们只记录最后一个元素是多少。\(记s为较大子序列结尾当前的数，t为较小子序列结尾的数，下面分类讨论\)\(当a[i]<=t<s时\)我们将a[i]既可以放进t所在的子序列，

给定一个长为\(n\)的序列\(a\)，你需要将该序列恰好分成两个子序列\(s,t\)。定义一个长为\(m\)的序列\(b\)的代价为\(\displaystylep(b)=\sum_{i=1}^{m-1}[b_i<b_{i+1}]\)，求\(p(s)+p(t)\)的最小值。每个测试点\(t\)组测试用例。思路贪心。可以发现答案的贡献只与