时间: 1000ms / 空间: 131072KiB / Java类名: Main
描述
求最长不下降子序列的长度
输入格式
第一行为n，表示n个数
第二行n个数
第二行n个数
输出格式
最长不下降子序列的长度
测试样例1
输入
3
1 2 3
输出
3
备注
N小于5000
for each num <=maxint
for each num <=maxint
居然把dp都忘了，唉。。。。
基础题，用f数组来存下降序列的长度，a数组保存数字
#include <cstdio>
#include <iostream>
using namespace std;int f[100000],a[100000];int main()
{int n,i,j,k;scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&a[i]);f[i]=1;}for(i=1;i<=n;i++){for(j=1;j<i;j++){if(a[j]<=a[i])f[i]=max(f[j]+1,f[i]);}}int Max=0;for(i=1;i<=n;i++)if(f[i]>Max)Max=f[i];printf("%d\n",Max);return 0;
}