最长上升子序列+最长递减子序列-重复的方法不严谨，貌似有人已经找到反例了，至于为什么那种方法能ac应该是测试数据弱吧
以下才是最标准的做法
//#pragma comment(linker, "/STACK:102400000,102400000") #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #ifdef _WIN32 typedef __int64 i64; #define out64 "%I64d\n" #define in64 "%I64d" #else typedef long long i64; #define out64 "%lld\n" #define in64 "%lld" #endif /************ for topcoder by zz1215 *******************/ #define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++) #define FOR(i,a,b) for( int i = (a) ; i <= (b) ; i ++) #define FF(i,a) for( int i = 0 ; i < (a) ; i ++) #define FFD(i,a,b) for( int i = (a) ; i >= (b) ; i --) #define S64(a) scanf(in64,&a) #define SS(a) scanf("%d",&a) #define LL(a) ((a)<<1) #define RR(a) (((a)<<1)+1) #define pb push_back #define pf push_front #define X first #define Y second #define CL(Q) while(!Q.empty())Q.pop() #define MM(name,what) memset(name,what,sizeof(name)) #define MC(a,b) memcpy(a,b,sizeof(b)) #define MAX(a,b) ((a)>(b)?(a):(b)) #define MIN(a,b) ((a)<(b)?(a):(b)) #define read freopen("in.txt","r",stdin) #define write freopen("out.txt","w",stdout) const int inf = 0x3f3f3f3f; const i64 inf64 = 0x3f3f3f3f3f3f3f3fLL; const double oo = 10e9; const double eps = 10e-9; const double pi = acos(-1.0); const int maxn = 101111; int n; int a[maxn]; vector v; inline void gao(int now) { if (v.empty() || now >= v[v.size() - 1]){ v.push_back(now); } else { v[upper_bound(v.begin(), v.end(), now) - v.begin()] = now; } } int main() { int T; cin >> T; while (T--){ cin >> n; for (int i = 1; i <= n; i++) { //cin >> a[i]; SS(a[i]); } v.clear(); int now; for (int i = n; i >= 1; i--) { now = 2 * a[i] + 1; gao(now); } for (int i = 1; i <= n; i++) { now = 2 * a[i]; gao(now); } cout << v.size() << endl; } return 0; }