时间限制
1000ms
空间限制
262144K
题目：
一只青蛙出去旅游，因为中国有一句古话说的好：“由简入奢易，由奢入俭难”，所以这只青蛙当看的当前景点比前面看过的景点差的时候，青蛙就会说“不开心”为了避免这只青蛙说“不开心”，并且使青蛙看的景点尽量的多，所以他请你帮忙给他安排一条线路，使青蛙可以看到尽量多的景点，并且不走回头路。
输入：
第一行为一个整数n，表示景点的数量
接下来n行，每行1个整数，分别表示第i个景点的质量
输出：
一个整数，表示青蛙最多可以看到几个景点
备注：
景点质量为1到n+23的整数
10<=n<23 10%
23<=n<233 30%
233<=n<2333 60%
2333<=n<23333 100%
样例输入：
10
3
18
7
14
10
12
23
30
16
24
样例输出：
6
题意：
一直青蛙旅行，他要去n个地点，每个地点有个有趣值，他去这个地点一定不能比他去过的地点的有趣点低，让你规定一条路线，使得他能尽可能到达最多的地点。
思路：
最长递增子序列模板题。
AC代码：
#include
#include
#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f
#define ONF 0xc0c0c0c0
using namespace std;
typedef long long LL;
int main()
{
int a[30000],n,dp[30000];
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
dp[i]=1;
}
int Max;
for(int i=1;i<=n;i++)
{
Max=0;
for(int j=1;j { if(a[j]<=a[i]) { Max=max(Max,dp[j]); } } dp[i]=Max+1; } int s=-1; for(int i=1;i<=n;i++) { s=max(s,dp[i]); } cout< } 注意点：求最长递增子序列有两种方法，第一种是用一个数组存有序的元素，然后两个数组求最长公共子序列，第二种是dp动态规划，显然在这里第一种方法行不通，要用第一种方法就要开一个二维dp，这里显然是开不了的，所以只有用第二种方法了。