ZJU 2136Longest Ordered Subsequence
#include<iostream>
#include<stdio.h> //Zju 用scanf,printf必须的
using namespace std;
#define N 1000
int v[N];//存放数值
int f[N];//辅助数组,存放LOS长度
//状态:f[i],以第i个元素(v[i])为最后一个元素的最长上升子序列的长度
//方程:f[i]=max(f[j]+1, f[i]), 0<=j<i && v[i]>v[j]
//初值:f[i]=1,0<=i<n,考虑只有v[i]一个数时的上升序列的长度
//结果:f[]中的最大值
int dpLos(int n)
{
int i, j, maxVal;
for(i=0;i<n;i++) f[i]=1;//每个数自己构成长度为1的升序序列
for(i=1;i<n;i++) //从第2个数开始算
{
for(j=0;j<i;j++)
{
if(v[i]>v[j] && f[i]<f[j]+1) //下降序列:v[i]<v[j]
{
f[i]=f[j]+1;
}
}
}
maxVal=f[0];
for(i=1;i<n;i++)
{
if (f[i]>maxVal) maxVal=f[i];
}
return maxVal;
}
void run(int now)
{
int i, n;
scanf("%d", &n);
for(i=0;i<n;i++) scanf("%d", &v[i]);
if (now>1) printf("\n");
printf("%d\n", dpLos(n));
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("e:\\input.txt","r",stdin);
#endif
int T, i;
scanf("%d", &T);
for(i=1; i<=T; i++) run(i);
return 0;
}
分享到:
相关推荐
zju 1642 Match for Bonus DP,滚存??zju 1642 Match for Bonus DP,滚存??zju 1642 Match for Bonus DP,滚存??zju 1642 Match for Bonus DP,滚存??zju 1642 Match for Bonus DP,滚存??
zju1001--1399的数据。全是.in和.out文件。
这个是浙江大学操作系统课程讲义,此部分为第2章,配套教材为操作系统的恐龙书
zju超强代码,大概有一半的题目吧,从别人那里弄的
zju电机学作业.pdf
zju 1025 Wooden Sticks http://acm.zju.edu.cn/show_problem.php?pid=1025
zju部分 解题报告zju部分 解题报告
cpp codes for zju.edu.cn problems
acm zju 额度cnacm zju 额度cnacm zju 额度cnacm zju 额度cnacm zju 额度cn
acm 新手必备 浙大 解答 代码库 zoj zju
zju 1048 Financial Managementhttp://acm.zju.edu.cn/show_problem.php?pid=1048
ZJU/zoj 题库上的部分题源码 本人博客: hi.baidu.com/xiaoxianxi_acm
zoj700代码,供acm爱好者研究学习,但请注意,切勿上交。
2、课后作业题6.8 3、Minimax 给一个只有叶子节点值的图 叉掉α-β pruning 4、贝叶斯网络 5、Markov Network 给一个Mark
zju题目与解答集合,学习ACM编程不可多得的好东西。
ZJU 题型分类 ZJU_Main 主页 下一页 ZJU 题型分类 文演整理版 2008-3-23 数论: 1007 Numerical Summation of a Series 简单题,还是蛮有意思的 1045 HangOver 简单题 1049 I Think I Need a Houseboat ...
zju动态规划试题选集 ,有ZOJ所有的动态规划题及其代码,很好的!!!
ZJU_V1.2.10.apk
zju 3406题 题目打包 http://hi.baidu.com/leokan/blog/item/baa1e6c48c9af5af8326acfa.html