贪心策略显然,读者自证不难。
第一问显然的最长下降子序列。
第二问用了一个神奇的贪心,大概是只要可以放在前面的任意一个系统后面就放,否则就新开一个。
有点坑的就是数据中可能有相同的高度,需要改一点点。
代码实现:
#include<bits/stdc++.h>
#define register signed
using namespace std;
const int MAXN=1005;
int n,k;
int a[MAXN],dp[MAXN];
vector<int>q;
int main()
{
while(~scanf("%d",&k))a[++n]=k;
for(register int i=1;i<=n;i++)
{
dp[i]=1;
for(register int j=1;j<i;j++)
if(a[i]<=a[j])dp[i]=max(dp[i],dp[j]+1);
}
int maxn=-0x7f7f7f7f;
for(register int i=1;i<=n;i++)
maxn=max(maxn,dp[i]);
printf("%d\n",maxn);
for(register int i=1;i<=n;i++)
{
bool flag=false;
for(register int j=0;j<q.size();j++)
if(a[i]<=q[j])
{
q[j]=a[i];
flag=true;
break;
}
if(!flag)q.push_back(a[i]);
}
printf("%d",q.size());
return 0;
}