单调递增最长子序列
描述
求一个字符串的最长递增子序列的长度
如:dabdbf最长递增子序列就是abdf,长度为4
输入
第一行一个整数0<n<20,表示有n个字符串要处理
随后的n行,每行有一个字符串,该字符串的长度不会超过10000
输出
输出字符串的最长递增子序列的长度
样例输入
3
aaa
ababc
abklmncdefg
样例输出
1
3
7
Accepted
#include<stdio.h>
int length(char * s)
{
int len[128] = {0}, i, t;
for(; *s != '\0' && (t = len[*s - 1] + 1); s++)
for(i = *s; i < 128 && len[i] < t; len[i++] = t);
return len[127];
}
int main()
{
int n;
char s[10001];
for(scanf("%d\n", &n); n--;)
printf("%d\n", length(gets(s)));
return 0;
}
还待好好研究研究。有IOCCC的风格啊
2、http://icpc.ahu.edu.cn/OJ/Problem.aspx?id=189
#include <iostream>
#include <cstring>
using namespace std;
#define MAXNUM 7005
int aMaxlen[MAXNUM]; // aMaxlen[]是备忘录
unsigned int array[MAXNUM];
unsigned int Maxlen(const int n) // Maxlen(n)是 以array[n]为末元素的所有递增子序列 中长度最长的列的长度
{
if( n == 1 )
return 1;
int i;
for(i = 1; i < n; i++) {
if (aMaxlen[i] == -1)
aMaxlen[i] = Maxlen(i);
}
int maxlen_i = 0; // maxlen_i是以array[i]为末元素的递增子序列中长度最长的列的长度,且array[i] < array[n]
for(i = 1; i < n; i++) {
if( array[i] < array[n] && aMaxlen[i] > maxlen_i )
maxlen_i = aMaxlen[i];
}
if( maxlen_i == 0 ) // maxlen_i没变,则array[n]最小(前面找不到比它小的)
return 1; // 故以array[n]为末元素的递增子序列就是它自己
return maxlen_i + 1;
}
int SearchMax(int size)
{
int max = 0;
for (int i = 1; i <= size; i++) {
if (aMaxlen[i] > max)
max = aMaxlen[i];
}
return max;
}
int main(void)
{
// freopen("cin.txt", "r", stdin);
int N;
while(cin >> N)
{
memset(aMaxlen, -1, sizeof(aMaxlen));
for(int i = 1; i <= N; i++)
cin >> array[i];
aMaxlen[N] = Maxlen(N);
cout << SearchMax(N) << endl;
}
return 0;
}
分享到:
相关推荐
澳泰AOL/AOJ5000系列智能流量积算显示控制仪表pdf,澳泰AOL/AOJ5000系列智能流量积算显示控制仪表:适用于自来水、油、液体、固态流体等无需补偿的工业过程流量参数的测量、显示、控制和计量积算。可接收孔板差压输入...
AOJ
(AOJ: sotetsuk, POJ: sotetsuk, AtCoder: sotetsuk) @nishimuuu (AOJ: nishimuuuuuu) @ryof(AOJ:ryof) @ chiiia12 (AOJ: chiiia12) @kikunantoka(AOJ:kikunantoka,AtCoder:kikunantoka) @toiroakr(AOJ:a_...
很小的框架,旨在通过在纯Java环境中引入面向方面的技术来增强设计的模块化。 无需配置文件,也不需要额外的构建步骤。
竞争性编程 竞技プログラミンミの练习で书いたコードです。
leetcode 1004 *LC 75problems => OK/NG => NG 表示我无法自己解决,所以我应该再次重新访问相同的问题。 ...NG日期已过级别名称类别NG 20200126全部/所有媒体20200126 20200125_esy_53_maximum_subarray.py ...
aojMain AOJ主系统
浙大的oj的代码,可以参考参考。。。。。。
AOJ2018 强大的在线代码编辑器 支持多国语言 更友好的用户界面 在线评委 安徽科技学院OJ系统。 1.设置管理员 insert into privilege(user_id,rightstr) values ( ' username ' , ' administrator ' ); 2.模板 cd...
程式设计 会津在线法官(AOJ),Codeforces等
aoj-cli 运行: python3 aoj/__main__.py 失败需安装相关依赖库 拓展其它oj 参考ctguoj / hihocoer 目录下代码, 实现aojOperate类 然后该改的改,能删的删... 功能列表: list -c | 列出所有正在进行的比赛 use id ...
やっつけ仕事から问题ID,ジャッジID,ソースコードを取得する。APIから,すべてのソースコードを取得できるが,言语,ステータスの情报がないのでjson形式で取得してみた。time,サーバに高负荷をかけないように...
learning_coding
福建澳泰AOD5000智能多通道巡检仪pdf,福建澳泰AOD5000智能多通道巡检仪
c语言实验报告c语言实验报告c语言实验报告c语言实验报告c语言实验报告c语言实验报告
leetcode 和 oj 描述 我对 , , , , , 中问题的解决方案, ...的政策,我不允许分享我的解决方案或相应的挑战问题。...DP Linq Search String Linq High-Accuracy DFS Backtracking Linked List String Stack (|) 外部链接
MC30P6240用户手册_V1.3.pdf
2018NOIP夏令营(提高组)数据结构习题讲课习题数组、链表、STLAOJ1220 删除重复AOJ1221 单词统计AOJ1051 约瑟夫问题CCF1109
AOJ AOJ矩阵状态的可用历史记录的完整JDK更新: AOJ OpenJ9 AOJ OpenJ9 Matrix状态的可用历史记录的完整JDK更新: 科雷托 有关Corretto Matrix状态的可用历史记录的完整JDK更新: 龙之井 有关Dragonwell Matrix...