最长单调递增子序列问题(动态规划)o()
// 最长单调递增子序列.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<iostream>
#define N 100
using namespace std;
//递归打印最长递增子序列
void print_it(char *str,int *pre,int last)
{
if(last==-1)
return;
else
{
print_it(str,pre,pre[last]);
cout<<str[last];
}
}
int _tmain(int argc, _TCHAR* argv[])
{
//存储原字符串
char str[N];
//len[j]存储到str[j]为止的最长递增子序列长度
int len[N];
//pre[j]存储到str[j]为止的最长递增子序列的前一个字符的位置
int pre[N];
int cases;
cout<<"请输入案例个数:"<<endl;
cin>>cases;
while(cases--)
{
cout<<"请输入字符串:"<<endl;
cin>>str;
//初始化各变量
int i;
int length = strlen(str);
for(i=0;i<length;i++)
{
len[i] = 1;
pre[i] = -1;
}
int j;
int max = 0;
for(j=1;j<length;j++)
{
for(i=0;i<j;i++)
{
max = 0;
if(str[j]>str[i])
{
max = len[i]+1;
if(max>len[j])
{
len[j] = max;
pre[j] = i;
}
}
}
}
//找最大的len[i]
//last为最长的递增子序列的最后一个字符的位置
max = 0;
int last;
for(i=0;i<length;i++)
{
if(len[i]>max)
{
max = len[i];
last = i;
}
}
cout<<"最长递增子序列的长度为:"<<max<<endl;
cout<<"最长递增子序列为:"<<endl;
print_it(str,pre,last);
cout<<endl;
}
system("pause");
return 0;
}
-----------------------------------------------程序测试----------------------------------------
请输入案例个数:
2
请输入字符串:
abceabf
最长递增子序列的长度为:5
最长递增子序列为:
abcef
请输入字符串:
abcabcdef
最长递增子序列的长度为:6
最长递增子序列为:
abcdef
请按任意键继续. . .
分享到:
相关推荐
acm模板(村村通,一笔画,最长单调不升序列等) 最长单调不升序列 问题描述 给定一个n个元素的数列a1,a2,…,an,求该序列中单调不升序列中最长者的长度。如34,78,53,36,40的最长单调不升序列有78,53,36或78...
12个ACM动态规划经典题 习题+分析+程序 (转载)
acm 动态规划 必做50题目
动态规划---做acm的人都知道,很难入门,本资源提供入门窗口
最长不下降子序列一些介绍
acm动态规划经典题,有助于增加对动态规划的理解与应用
本次课程论文,针对ACM比赛中的经典算法,动态规划,进行了详细的讲述,并以ZOJ和POJ上的经典题目为例,讲述了动态规划算法的应用。
基于C++的ACM模板
acm 平衡规划平衡规划平衡规划平衡规划平衡规划平衡规划平衡规划平衡规划
ACM模板和一些题目的代码实现c++源码.zipACM模板和一些题目的代码实现c++源码.zipACM模板和一些题目的代码实现c++源码.zipACM模板和一些题目的代码实现c++源码.zipACM模板和一些题目的代码实现c++源码.zipACM模板和...
ACM 编程 算法 之动态规划 课件讲义
ACM ICPC程序设计与分析(C++实现)全本,挺厚的一本书,看的时候抓住关键点去看
ACM中的动态规划中的状态压缩问题,有讲解和例题。
详细解释了动态规划算法的各种应用场合,对于做ACM题很有帮助
该课件详细讲述了acm方面关于动态规划法的原理,有背包原型,有最大子段和,有最长连续子序列,最短路径等等。
acm吃糖果的题目,自己根据提示写的比较简单的代码,欢迎指正
最长公共子序列模版
暑假学校ACM集训用的课件,动态规划专题。
ACM,参考资料,课件,算法,最短路,动态规划