题目描述:
Redraiment是走梅花桩的高手。Redraiment可以选择任意一个起点,从前到后,但只能从低处往高处的桩子走。他希望走的步数最多,你能替Redraiment研究他最多走的步数吗?
本题含有多组样例输入
输入描述:
输入多组数据,1组有2行,第1行先输入数组的个数,第2行再输入梅花桩的高度
输出描述:
一组输出一个结果
示例:
输入:
6
2 5 1 5 4 5
3
3 2 1
输出:
3
1
说明:
6个点的高度各为 2 5 1 5 4 5
如从第1格开始走,最多为3步, 2 4 5
从第2格开始走,最多只有1步,5
而从第3格开始走最多有3步,1 4 5
从第5格开始走最多有2步,4 5
所以这个结果是3。
解题思路:
这道题是个标准的最长升序子序列问题,用动态规划求解。v存放梅花桩高度信息,result用来作动态规划表,每个位置对应的result值就是截止到当前遍历时间点时的最大行进步数;从前向后遍历梅花桩,每到某个位置,再遍历该位置前的梅花桩,若前面的位置低于当前位置,则刷新当前位置的result值,刷新结果为当前位置result值和前面位置result值+1这两者间的最大值;这样每个位置的result值动态刷新,直到遍历全部完成后,result值最大的数值就是结果。
测试代码:
#include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { int num; while(cin>>num) { vector<int> v; for(int i=0;i<num;++i) { int temp; cin>>temp; v.push_back(temp); } vector<int> result(num,1); for(int i=0;i<num;++i) { for(int j=0;j<i;++j) { if(v[j]<v[i]) { result[i]=max(result[i],result[j]+1); } } } int max = *max_element(result.begin(), result.end()); cout<<max<<endl; } return 0; }