[编程题]Redraiment的走法
- 热度指数：199841 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
第一行输入一个整数
代表梅花桩的数量。
个整数
代表每一个梅花桩的高度。
输出描述:
示例1
输入
6 2 5 1 5 4 5
输出
3
说明
。
。
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
int main()
{
int n;
vector<int>nums;
while(cin>>n)
{
nums.clear();
for(int i=0;i<n;++i)
{
int x;
cin>>x;
nums.push_back(x);
}
//add your code
vector<int>dp(n+1,1);
int maxLen=1;
for(int i=1;i<=n;++i)
{
for(int j=1;j<i;++j)
{
if(nums[i-1]>nums[j-1] && dp[j]+1>dp[i])
{
dp[i]=dp[j]+1;
maxLen=max(dp[i],maxLen);
}
}
}
cout<<maxLen<<endl;
}
return 0;
}
发表于 2017-02-03 12:18:55
回复(0)
d什么p，给我搜
#include<stdio.h>
int n;
int h[201]={0};
int res = 1;
void dfs(int start,int ans)
{
for(int i=start+1;i<n;i++)
{
if(h[i]>h[start])
{
ans++;
dfs(i,ans);
if(ans>res)res=ans;
ans--;
}
}
}
int main()
{
int res2=-1;
while(scanf("%d",&n)!=EOF)
{
res2=-1;
for(int i=0;i<n;i++)
{
scanf("%d",&h[i]);
}
for(int i=0;i<n;i++)
{
res = 1;
dfs(i,1);
//printf("%d = %d\n",i,res);
if(res>res2)res2=res;
}
printf("%d\n",res2);
}
return 0;
}
发表于 2021-11-27 23:34:42
回复(0)
典型的最长上升子序列问题，可以使用动态规划。
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
int[] arr = new int[n];
for(int i=0;i<arr.length;i++) {
arr[i] = sc.nextInt();
}
int[] dp = new int[n];
Arrays.fill(dp, 1);
int maxLen = 1;
for(int i=0;i<arr.length;i++) { // 2 5 1 5 4 5
for (int j=0;j<i;j++) {
if (arr[i] > arr[j]) {
dp[i] = Math.max(dp[i], dp[j]+1); // 借助dp[j]来更新dp[i]
}
}
maxLen = Math.max(maxLen, dp[i]);
}
System.out.println(maxLen);
}
}
}
发表于 2021-03-25 15:15:24
回复(0)
#include
#include
using namespace std;
int main()
{
int n;
while(cin >> n)
{
if(n < 1)
{
cout << "0";
return 0;
}
vector num(n);
for(int i=0;i<n;++i)
{
cin >> num[i];
}
vector dp(n,1);
int max_step = 1;
for(int i=1;i<n;++i)
{
int max_num = 0;
for(int j=0;j<i;++j)
{
if(num[i] > num[j] && dp[j] > max_num)
{
max_num = dp[j];
}
}
dp[i] += max_num;
max_step = max(max_step,dp[i]);
}
cout << max_step << endl;
}
return 0;
}
发表于 2020-07-23 23:53:33
回复(0)
#include <stdio.h>
//动态规划之最大递增序列
int main()
{
int i,j,n,num[1024],max;
while(scanf("%d",&n) != EOF)
{
int dp[1024];
for(i=0; i<n; i++)
{
scanf("%d",&num[i]);
dp[i] = 1;
}
for(j=1; j<n; j++)
for(i=0; i<j; i++)
if( num[j]>num[i] && dp[j]<dp[i]+1)
dp[j] = dp[i]+1;
for(i=1,max=dp[0]; i<n ; i++)
if(dp[i] > max)
max = dp[i];
printf("%d\n",max);
}
return 0;
}
发表于 2020-04-13 19:32:42
回复(0)
#时间复杂度nlog（N）
try:
while True:
num,digitsList = int(input()),list(map(int,input().split()))
subSeries = []
maxLen = 0
subSeries.append(digitsList[0]) #辅助数组，如果该数组有记录的话,如果你比该数组的最后一个数大的话，最大递增子序列加一
#否则在里面查找到比你大的最小数替换掉，在数组的下标其实就是以该数结尾的最长子序列长度
for i in range(1,num):
if digitsList[i] > subSeries[maxLen]:
maxLen += 1
subSeries.append(digitsList[i])
else:
left,right = 0,maxLen
while left <= right: #在已有的subSeries数组范围内二分查找到比该数大的最小数替换掉
mid = (left+right)//2
if digitsList[i] > subSeries[mid]:
left = mid+1
else:
right = mid-1
subSeries[left] = digitsList[i]
# print(" ".join(map("{:>2}".format, subSeries))) #可以每次打印出来观察变化
print(maxLen+1)
except Exception:
pass
编辑于 2018-10-22 22:34:49
回复(0)
#include <iostream>
using namespace std;
int GetResult(int num, int pInput[])
{
int *dp = new int[num];
int i, j, pResult = 1;
for(i = 0; i < num; i++)
{
dp[i] = 1;
for(j = 0; j < i; j++)
{
if(pInput[j] < pInput[i] && dp[j] + 1 >= dp[i])
{
dp[i] = dp[j] + 1;
}
if(dp[i] > pResult) pResult = dp[i];
}
}
return pResult;
}
int main()
{
int num;
while(cin >> num)
{
int *pInput = new int[num];
for(int i = 0; i < num; i++) cin >> pInput[i];
cout << GetResult(num, pInput) << endl;
}
return 0;
}
发表于 2018-07-27 16:02:29
回复(0)
//
// main.cpp
// Redraiment是走梅花桩的高手。Redraiment总是起点不限，从前到后，往高的桩子走，但走的步数最多，不知道为什么？
// 你能替Redraiment研究他最多走的步数吗？
//
// 算法：求最长上升子序列的长度
// Created by Rain on 16/03/2017.
// Copyright © 2017 Rain. All rights reserved.
//
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
string str="";
int n=0;
while(cin>>n)
{
vector<int> vec;
int maxlen[1000];
int in=0;
for(int i=0;i<n;i++)
maxlen[i]=1;
while(n--)
{
cin>>in;
vec.push_back(in);
}
for(int i=1;i<vec.size();i++)
{
int max=0;
for(int j=i-1;j>=0;j--)
{
if(vec[i]>vec[j]&&maxlen[j]>max)
{
max=maxlen[j];
}
maxlen[i]=max+1;
}
}
int max=0;
for(int i=0;i<vec.size();i++)
{
if(max<maxlen[i])
max=maxlen[i];
}
cout<<max<<endl;
}
return 0;
}
发表于 2017-03-16 16:25:33
回复(0)
// 最长上升子序列
#include <iostream>
#include <stdio.h>
using namespace std ;
int arr[ 1000 ];
int dp[ 1000 ];
int main()
{
int n;
while ( cin >>n)
{
for ( int i= 0 ;i<n;i++)
scanf ( "%d" ,& arr [i]);
dp [ 0 ] = 1 ;
int mmax= 0 ;
for ( int i= 1 ;i<n;i++)
{
mmax = 1 ;
for ( int j= 0 ;j<i;j++)
{
if ( arr [j] < arr [i])
if ( dp [j]+ 1 >= mmax)
mmax = dp [j]+ 1 ;
}
dp [i] = mmax;
}
mmax = 1 ;
for ( int i= 0 ;i<n;i++)
if ( dp [i] > mmax)
mmax = dp [i];
/*for(int i= 0 ;i<n;i++)
cout<<dp[i]<<" "<<arr[i]<<endl;
*/
cout <<mmax << endl ;
}
return 0 ;
}
发表于 2017-02-06 20:40:30
回复(1)
#include<stdio.h>
int main()//动态规划实现最长升序数组子串
{
int n;
while(scanf("%d",&n)==1)
{
if (n>0)
{
int a[100];
int dp[100];
for (int ii=0; ii<n; ii++)
{
scanf("%d",&a[ii]);
}//输入
dp[0] = 1;
for (int i=1; i<n; i++)
{
dp[i] = 1;
for (int j=0; j<i; j++)
{
if (a[i] > a[j])
{
if (dp[i] < dp[j]+1)
{
dp[i] = dp[j]+1;
}
}
}
}
int max=dp[0]; //统计最大步数
for (int k=1; k<n; k++)
{
if (max<dp[k])
{
max=dp[k];
}
}
printf("%d\n",max);
}
}
}
发表于 2016-08-24 14:55:17
回复(0)
#include<vector>
#include<iostream>
using namespace std;
int main()
{
int line;
while (cin >> line)
{
vector<int>vec;
int *max = new int[line]; //max[0]表示从0点出发最大的步数
int *arr = new int[line];//arr[i]表示从某个点出发到i点的最大步数
int tmp;
for (int i = 0; i<line; i++)
{
cin >> tmp;
vec.push_back(tmp);
}
int out=1;
for (int i = 0; i < line; i++)
{
max[i] = 1;
arr[i] = 1;
int flag = vec[i];
for (int j = i+1; j < line; j++)
{
if (vec[j] > flag)
{
int tmp = j - 1;
int maxtmp=1;
while (tmp > i)
{
if (vec[tmp] < vec[j])
{
if (arr[tmp] > maxtmp)
maxtmp = arr[tmp];
}
tmp--;
}
arr[j] = maxtmp + 1;
}
else
arr[j] = 0;
}
for (int k = i + 1; k < line; k++)
{
if (arr[k]>max[i])
max[i] = arr[k];
}
}
for (int i = 0; i < line; i++)
{
if (out < max[i])
out = max[i];
}
cout << out << endl;
}
}
发表于 2016-08-18 23:00:40
回复(0)
//最长递增子序列问题
int getHeight(vector<int> men, int n) {
// write code here
int *help=new int[n];//辅助数组，存放以i为下标的最大增长子序列个数
for(int i=0;i<n;i++)//初始化，假设都是以自己为尾的增长子序列最小为1个
help[i]=1;
int max=1;
for(int i=1;i<n;i++)
{
int j=0;
while(j<i)
{
if(men[j]<men[i] && help[j]>help[i]-1)
{
help[i] = help[j]+1;
if(max<help[i])
max=help[i];
}
j++;
}
}
return max;
}
int main()
{
int N;
while(cin>>N)
{ vector<int> vec; int temp;
for(int i=0;i<N;i++)
{
cin>>temp;
vec.push_back(temp);
}
cout<<getHeight(vec,N)<<endl;
}
return 0;
}
发表于 2016-08-18 18:42:16
回复(0)
#include <iostream>
#include <vector>
using namespace std;
//这个题目本质就是，最长递增子序列的问题
int main ()
{
int n;
while( cin>>n)
{
vector<int> f(n, 1);//dp
vector<int> arry(n, 0);
for(int i = 0; i < n;i++)
cin>>arry[i];
int themax = 1;
for(int i = 1; i < n; i++){
for(int j = i-1; j >= 0; j--){
if(arry[i]>arry[j] && (f[j]+1)>f[i]){
f[i] = f[j]+1;
if(f[i] > themax)
themax = f[i];
}
}
}
cout<<themax<<endl;
}
return 0;
}
发表于 2016-07-10 11:28:22
回复(0)
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;
import java.util.Iterator;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int N=sc.nextInt();
int[] x=new int[N];
Set<Integer> set=new TreeSet<>();
for(int i=0;i<N;i++){
x[i]=sc.nextInt();
set.add(x[i]);
}
int[] y=new int[set.size()];
int j=0;
Iterator<Integer> it=set.iterator();
while(it.hasNext()){
Integer i=it.next();
y[j++]=i;
}
int[][] c=Lsc(x, y);
}
}
public static int[][] Lsc(int[] x,int[] y){
int[][] c=new int[x.length+1][y.length+1];
for(int i=1;i<x.length+1;i++){
for(int j=1;j<y.length+1;j++){
if(x[i-1]==y[j-1]){
c[i][j]=c[i-1][j-1]+1;
}else if(c[i-1][j]>=c[i][j-1]){
c[i][j]=c[i-1][j];
}else if(c[i-1][j]<c[i][j-1]){
c[i][j]=c[i][j-1];
}
}
}
System.out.println(c[x.length][y.length]);
return c;
}
}
这里先将序列转化为一个不重复的递增的序列，然后与原序列求最长公共子列。。。用到了简单的动态规划，，，，
发表于 2016-06-25 22:21:08
回复(0)
本质是求 最长递增子序列 ，这题用动态规划即可，LeetCode还有更高效的方法 [最长递增子序列](https://leetcode-cn.com/problems/longest-increasing-subsequence/)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int[] arr = new int[scanner.nextInt()];
for (int i = 0; i < arr.length; i++) {
arr[i] = scanner.nextInt();
}
int maxLength = -1;//避免数组为空
int[] dp = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLength = Math.max(dp[i], maxLength);
}
System.out.println(maxLength + 1);
}
}
}
发表于 2021-07-22 08:56:23
回复(0)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <cctype>
#include <vector>
#include <stack>
#include <map>
using namespace std;
int main()
{ int n; while(cin>>n) { vector<int> a(n,0); vector<int> dp(n,1); int s = 0; for(int i=0;i<n;i++) { cin>>a[i]; for(int j=0;j<i;j++) if(a[j]<a[i]) dp[i] = max(dp[i],dp[j]+1); s = max(s,dp[i]); } cout<<s<<endl; } return 0;
}
发表于 2018-06-26 00:33:29
回复(0)
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int num=0,ret=0;
vector<int> vec;
cin>>num;
while (num--)
{
int tmp=0;
cin>>tmp;
vec.push_back(tmp);
}
int n=vec.size();
vector<int>dp(n,1);//最小子序列初始化为1
//dp[i]为vec[i]为结尾的最长增长子序列长度
for (int i=0;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(vec[i]>vec[j])//比vec[i]小的即可
dp[i]=max(dp[i],dp[j]+1);
//选择最大前一个dp作为递增序列f[i] = max{f[i],f[j]+1},1<=j<i,a[j]<a[i].
}
ret=max(dp[i],ret);
}
cout<<ret<<endl;
system("pause");
return 0;
}
求各位大神帮忙,我在VS上能编译成功,在牛客网上就是不行
发表于 2017-08-04 16:02:06
回复(2)
闹了半天，就是个最长上升子序列的问题。。
这种问题要使用动态规划方法来解，一种时间复杂度为O(n)2，另一种为nlog(n)。提供一种nlog(n)的解法：
import bisect
while True:
try:
a, b = int(input()), map(int, input().split())
q = []
for v in b:
pos = bisect.bisect_left(q, v)
if pos == len(q):
q.append(v)
else:
q[pos] = v
print(len(q))
except:
break
编辑于 2019-04-09 21:47:49
回复(15)
利用动态规划求解，整个问题可以转换为从前到后到第几个桩走的步数最多。解析写在注释中(python版)：
def GetResult(l):
n=len(l) # 传入list的长度
dp=[1]*n # dp[i]表示以第i个桩为结尾，最多走多少步，初始是1步（默认这个桩是跟它之前相比最矮的）
res=0 # 整个问题的结果
for i in range(n):# i表示第几个桩
for j in range(i):# j表示i前面的桩
if l[i]>l[j]: # 如果第i个桩前面有比它矮的（比如是j），
# 且以第j个桩为结尾走的步数是最多的，
# 步数就是dp[j]+1，加的这个1表示从第j个走1步到第i个桩；另一种就是dp[i],默认等于1，但是
# 遍历j的过程可能会更新这个值，因此取上述两个结果中最大的那个值，表示第i个桩为结尾，
# 最多走多少步
dp[i]=max(dp[i],dp[j]+1)
res=max(res,dp[i])# 到第i个桩时最多走几步
return res
while True:
try:
n=int(input())#几个点
str_input=input().split()
l=[int(v) for v in str_input]# 输入的数组成的集合
# l=[2,5,1,5,4,5]
# print(l)
ans=GetResult(l)
print(ans)
except:
break
发表于 2020-02-16 13:22:49
回复(9)
问题信息
难度：
320条回答
2894收藏
44021浏览
通过挑战的用户
查看代码-
2023-02-23 10:30:44
-
2023-01-07 17:35:50 -
2022-10-15 10:45:27 -
2022-09-16 17:11:18 -
2022-09-16 17:05:54
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
