「Solution」华一高ks10.5 T2 & P1970 花匠

(Updatedspace2020.10.31)：更正证明

思路和洛谷第一篇题解类似，但是第一篇题解是能够被hack的，hack数据：

1
1

题解输出2，答案1。

这里给出更完善的写法。

首先，回顾一下求非降子序列的写法：

int a[MAXN], d[MAXN];
int dp() {
  d[1] = 1;
  int ans = 1;
  for (int i = 2; i <= n; i++) {
    for (int j = 1; j < i; j++)
      if (a[j] <= a[i]) {
        d[i] = max(d[i], d[j] + 1);
        ans = max(ans, d[i]);
      }
  }
  return ans;
}

(O(n^2)) From OI Wiki

考场上，我就是按照非降子序列的思路AC了这道题。

AC Code

#include<bits/stdc++.h>
using namespace std;
int h[100005], ans1, ans2, f1 = 1, f2 = -1, n;
int cmp(int a, int b){
	if(a > b) return 1;
	else if (a < b) return -1;
	else return 0;
}
int main(){
//	freopen("flower.in", "r", stdin);
//	freopen("flower.out", "w", stdout);
	cin >> n;
	for(int i = 0; i < n; i++) cin >> h[i];
	ans1 = ans2 = 1;
	for(int i = 1; i < n; i++){
		if(cmp(h[i], h[i-1]) == f1) ans1++, f1 *= -1;
		if(cmp(h[i], h[i-1]) == f2) ans2++, f2 *= -1;
	}
	cout << max(ans1, ans2);
	return 0;
}

解题方法

常规来讲，这个部分应该放在代码前面，但是对于这么一道题，我认为先看代码再看讲解会更好。

有两种不同情况，ans1考虑输入数据中满足条件(A)的最长序列，ans2则考虑条件(B)，输出时比较两者最终结果取较大者即可。

cmp函数是为了方便做比较。

f1和f2数组分别是ans1和ans2的flag，代表序列(g)的下一个元素相比与末尾元素应该更大还是更小。

读懂代码应该没有什么难度，那么接下来，我们注意到，非降子序列复杂度是(O(n^2))，而上面的代码虽然思路和非降子序列一样，但复杂度是线性的，那么，我们来证明以上算法的正确性。

首先，设原序列为(A)，新序列为(B)，并且此时，由(A_{1...n})已经构成了(B_{1...m})。

(B_{m-1}>B_{m})和(B_{m-1}<B_{m})这两种情况是等价的，那么只讨论前者。

现在，程序在等待第一个(A_i>A_{i-1})的数，假设(B_m>...>A_{n+1}>A_{n+2}>...>A_{k-1})，而(A_k>A_{k-1})，那么现在，我们只需要将(B_m)更改为(A_{k-1})，因为我们一定可以保证(A_{k-1} < B_m)，然后再把(A_k)作为(B_{m+1})即可，序列长度+1​，(Q.E.D.)

大水题