今天考试崩出翔了，去NOIP2013排遣一下
题目简述：给你一个长度为n的序列，要你输出最长上升序列的长度和最长下降序列的长度中的最小值
呵呵，水，我们来DP吧，作为一个穷人，我们要节约内存，所以我决定不开DP数组，我们用a来记录当前最长上升序列的长度，用b记录最长下降序列的长度，一边输入，一边更新，总共只有5个int型变量
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> using namespace std; typedef long long ll; int main(){ int n,h,g; int a = 1,b = 1; scanf("%d%d",&n,&g); while(n--){ scanf("%d",&h); if (h > g) a = max(a,b + 1); if (g > h) b = max(b,a + 1); g = h; } printf("%d\n",max(a,b)); return 0; }
原文：http://www.cnblogs.com/GENEVE/p/4814545.html