总时间限制: 2000ms 内存限制: 65536kB
描述
一个数的序列bi，当b1 <b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1,a2, ..., aN)，我们可以得到一些上升的子序列(ai1,ai2, ...,aiK)，这里1 <=i1 < i2 < ... <iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8). 你的任务，就是对于给定的序列，求出最长上升子序列的长度。
输入
输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。
输出
最长上升子序列的长度。
样例输入
7 1 7 3 5 9 4 8样例输出
4来源
翻译自 Northeastern Europe 2002, Far-Eastern Subregion 的比赛试题
虽然这真的是一道特别特别水的动态规划题= =但水题也是题！！！
于是乎我就干脆就这样把代码弄上来吧。。
#include<cstdio> int a[10010]={-10},f[10010],n; int main() { int i,j; scanf("%d",&n); a[n+1]=20000; for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;i<=n+1;i++) for(j=0;j<=i-1;j++) if(a[j]<a[i]&&f[j]>=f[i]) f[i]=f[j]+1; printf("%d",f[n+1]-1); }
这就是我做的一点都不酷炫的代码= =
反正就是那什么阶段最优然后全局最优那什么玩意的qwq
然后此处省略一万字= =
反正就是把前面找到的最好的解给neng过来omg原谅我的语文。。我是真的不知道怎么说= =
一次AC也是可以很容易做到的= =
