全题最短用时!!0ms-by SJZ08

下降子序列+贪心

#include <iostream>
#include <algorithm>
using namespace std;
int a[100005];
int dp[100005];
bool v[100005]; 
int main() {
	int n=1;
	while (cin>>a[n]) n++;
	n--;
	int maxk=-1e9,ans=0;
	dp[1]=1;
	for (int i=2;i<=n;i++) {
		dp[i]=1;
		for (int j=i-1;j>=1;j--) {
			if (a[j]>=a[i]) {
				dp[i]=max(dp[i],dp[j]+1);
			}
		}
		maxk=max(maxk,dp[i]);
	}
	for (int tmp=n;tmp>0;) {
		int h=1e9;
		ans++;
		for (int i=1;i<=n;i++) {
			if (a[i]<h&&v[i]==0) {
				h=a[i];
				v[i]=1;
				tmp--;
			}
		}
	}
	printf("%d\n%d",maxk,ans);
	return 0;
}