[NOIP1999]拦截导弹

就是求最长不上升子序列和最长不上升子序列的最少数量
根据dilworth定理我们知道可划分的最少不上升子序列的数目就是其最长下降子序列的长度。

#include
#include
#include
#include
#include
#include
#define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
typedef long long ll;

int a[N], dp1[N], dp2[N];

void work() {
	int cnt = 1;
	while (cin >> a[cnt]) {
		dp1[cnt] = dp2[cnt] = 1;
		cnt++;
	}
	cnt--;
	for (int i = 1; i <= cnt; i++)
		for (int j = 1; j < i; j++) {
			if (a[i] <= a[j]) dp1[i] = max(dp1[j] + 1, dp1[i]);
			if (a[i] > a[j]) dp2[i] = max(dp2[j] + 1, dp2[i]);
		}
	int ans1 = -INF, ans2 = -INF;
	for (int i = 1; i <= cnt; i++) {
		ans1 = max(ans1, dp1[i]);
		ans2 = max(ans2, dp2[i]);
	}
	cout << ans1 << 'n' << ans2 << 'n';
}

int main() {
	BUFF;
	
		work();
	return 0;
}