华为OJRedraiment的走法

ゝ一世哀愁。 2022-06-17 06:49 171阅读 0赞

<table style="border-spacing:0px; border-collapse:collapse; width:960px; margin-bottom:35px; table-layout:fixed; color:rgb(92,92,92); font-family:glober,'Helvetica Neue',Helvetica,Arial,'Lantinghei SC','Hiragino Sans GB','Microsoft YaHei','Wenquanyi Micro Hei',sans-serif; font-size:14px; line-height:20px"> 
 <tbody style=""> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 描述</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> <pre style="overflow:hidden; font-family:monospace,monospace; font-size:1em; white-space:pre-wrap; word-wrap:break-word; line-height:24px">题目描述&nbsp;&nbsp;&nbsp;&nbsp;Redraiment是走梅花桩的高手。Redraiment总是起点不限，从前到后，往高的桩子走，但走的步数最多，不知道为什么？你能替Redraiment研究他最多走的步数吗？&nbsp;&nbsp;样例输入62&nbsp;5&nbsp;1&nbsp;5&nbsp;4&nbsp;5&nbsp;样例输出3&nbsp;提示Example:&nbsp; 6个点的高度各为&nbsp;2&nbsp;5&nbsp;1&nbsp;5&nbsp;4&nbsp;5&nbsp; 如从第1格开始走,最多为3步,&nbsp;2&nbsp;4&nbsp;5&nbsp; 从第2格开始走,最多只有1步,5&nbsp; 而从第3格开始走最多有3步,1&nbsp;4&nbsp;5&nbsp; 从第5格开始走最多有2步,4&nbsp;5所以这个结果是3。&nbsp;接口说明方法原型：&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;GetResult(int&nbsp;num,&nbsp;int[]&nbsp;pInput,&nbsp;List&nbsp;&nbsp;pResult);输入参数： &nbsp;&nbsp;&nbsp;int&nbsp;num：整数，表示数组元素的个数（保证有效）。 &nbsp;&nbsp;&nbsp;int[]&nbsp;pInput:&nbsp;数组，存放输入的数字。输出参数： &nbsp;&nbsp;&nbsp;List&nbsp;pResult:&nbsp;保证传入一个空的List，要求把结果放入第一个位置。 返回值： &nbsp;&nbsp;正确返回1，错误返回0&nbsp;&nbsp;&nbsp;</pre> </td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 知识点</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 排序</td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 运行时间限制</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 10M</td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 内存限制</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 128</td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 输入</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 输入多行，先输入数组的个数，再输入相应个数的整数 </td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 输出</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 输出结果 </td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 样例输入</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 6 2 5 1 5 4 5</td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 样例输出</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 3</td> 
 </tr> 
 </tbody> 
</table>

#include <iostream> 
 #include <vector>
 #include <string>
 #include <algorithm>
 
 using namespace std;
 
 int GetUpSeries(vector<int> src)
 {
 	int N = src.size();
 	vector<int> dst;
 	dst.resize(N);
 	for (int i = 0; i < N; i++)
 	{
 		dst[i] = 1;
 	}
 
 	for (int i = 0; i < N; i++)
 	{
 		for (int j = 0; j < i; j++)
 		{
 			if (src[j]<src[i] && dst[j] + 1>dst[i])
 			{
 				dst[i] = dst[j] + 1;
 			}
 		}
 	}
 
 	int max = 0;
 	for (int i = 0; i < N; i++)
 	{
 		if (dst[i]>max)
 			max = dst[i];
 	}
 	return max;
 }
 void main()
 {
 	int N;
 	cin >> N;
 	vector<int> vec;
 	for (int i = 0; i < N; i++)
 	{
 		int tmp;
 		cin >> tmp;
 		vec.push_back(tmp);
 	}
 
 	cout << GetUpSeries(vec) << endl;
 }