首页 > 试题广场 >

Redraiment的走法

[编程题]Redraiment的走法

热度指数：183541 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

Redraiment是走梅花桩的高手。Redraiment可以选择任意一个起点，从前到后，但只能从低处往高处的桩子走。他希望走的步数最多，你能替Redraiment研究他最多走的步数吗？

数据范围：每组数据长度满足 $1 \le n \le 200 \$ ，数据大小满足 $1 \le val \le 350 \$

输入描述:

数据共2行，第1行先输入数组的个数，第2行再输入梅花桩的高度

输出描述:

输出一个结果

示例1

输入

6
2 5 1 5 4 5

输出

说明

6个点的高度各为 2 5 1 5 4 5
如从第1格开始走,最多为3步, 2 4 5 ，下标分别是 1 5 6
从第2格开始走,最多只有1步,5
而从第3格开始走最多有3步,1 4 5， 下标分别是 3 5 6
从第5格开始走最多有2步,4 5， 下标分别是 5 6
所以这个结果是3。

算法知识视频讲解

小小呆萌坤

使用系统；使用System.Collections.Generic；使用System.Linq;使用System.Text.RegularExpressions;命名空间Test0001 {班级计划{公共静态无效的Main（字符串[] args）{弦线；而（！string.IsNullOrEmpty （行= Console.ReadLine（）））Func（行）；} // 30 // 186 13 322 264 328 110 120 73 20 35 240 97 150 221 284 324 46 219 239 284 128 251 298 *** 304 36 144 236 163 122公共静态无效Func（字符串行）{var arr = Console.ReadLine（）。Trim（）。Split（”）。Select（x => int.Parse（x））。ToArray（）； int len = arr.Length; int [] res =新的int [len];为（int i = 1;我<len; i ++）{//找到比当前数小的前面所有的数int val = arr [ i];对于（int j = i-1; j> = 0; j-）{如果（arr [j] <val）{res [i] = Math.Max（res [j] + 1，res [ i]）；}}} Console.WriteLine（res.Max（）+ 1）；}}}

解释一下2 5 1 5 4 5
我要求最后一个5他最大可以连续几个的话，我是不是就得知道他前面所有比他小的都可以连续几个

然后找到最大连续之后加上我自己，也就是加一，即为我当前最大连续数

arr用来记录最大连续数量

第一位不管多少金额0

第一次2 5 1 5 4 5

0 1

第二次2 5 1 5 4 5

0 1 0

第三次2 5 1 5 4 5

0 1 0？

这里发现2和1都比5小因此(2-> 0) + 1 (1-> 0) + 1和自己的0比发现0 + 1最大因此得

第四次2 5 1 5 4 5

0 1 0 1？

同理2 1都比4小

第五次2 5 1 5 4 5

0 1 0 1 1？

这里发现2和1和4都比5小因此（2-> 0）+ 1，（1-> 0）+ 1，（4->1）+1和自己的0比发现1 + 1最大因此得

第六次2 5 1 5 4 5

0 1 0 1 1 2

因此最大长度arr中高度+ 1两个比5小所以一共3个数

编辑于 2020-04-23 16:14:16 回复(0)

joykechen

#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)

HelloWorld#5190

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)

Java

jarsing

典型的最长上升子序列问题，可以使用动态规划。
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)

牛客44738297号

python最长上升子序列问题

#(1)利用二分查找库函数
import bisect
while True:
    try:
        n = int(input())
        nums = list(map(int, input().split()))
        queue = []
        for num in nums:
            if not queue or num > queue[-1]:
                queue.append(num)
            else:
                location = bisect.bisect_left(queue, num)
                queue[location] = num
        print(len(queue))
    except:
        break


#(2)自己写二分查找函数
def binary(nums, target):
    left = 0
    right = len(nums)-1
    while left < right:
        mid = (left + right) // 2
        if target == nums[mid]:
            return mid
        elif target < nums[mid]:
            right = mid
        else:
            left = mid + 1
    return right
while True:
    try:
        n = int(input())
        nums = list(map(int, input().split()))
        queue = []
        for num in nums:
            if not queue or num > queue[-1]:
                queue.append(num)
            else:
                location = binary(queue, num)
                queue[location] = num
        print(len(queue))
    except:
        break

发表于 2021-02-23 09:21:35 回复(1)

H2ongZh

差评，样例给的输入格式与更多测试格式不同，样例：6，2/n 3/n ....

更多的样例是空格一行数字，可能对c++无所谓，但是用别的语言可能有问题

发表于 2020-08-19 05:49:31 回复(0)

C/C++

J.Fan

#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)

学近伞

最简单的python的算法，递归。缺点是时间复杂度是2^n的，没有实用价值。优点是简单，小伙伴门赶紧学起来：

def opt(arr):
    if(len(arr) == 1):
        return 1
    elif(len(arr) == 0):
        return 0
    else:
        new_arr = [num for num in arr if num >arr[0] ]
        return max(opt(new_arr)+1,opt(arr[1:]))

def no_rec_opt(arr,len):
    dp = len*[1]
    dp[0] = 1
    for i in range(1,len):
        dp_choose = 1
        for j in range(0,i):
            if(arr[j]<arr[i]):
                dp_choose = max(dp_choose,dp[j]+1)
        dp[i] = dp_choose
    return max(dp)

def no_rec_opt(arr,len):
    dp = len*[1]
    dp[0] = 1
    for i in range(1,len):
        dp_choose = 1
        for j in range(0,i):
            if(arr[j]<arr[i]):
                dp_choose = max(dp_choose,dp[j]+1)
        dp[i] = dp_choose
    return max(dp)

编辑于 2020-05-01 15:26:14 回复(0)

C/C++

牛客227521256号

#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)

Python

TimeMac

#时间复杂度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)

RainChang

//
//  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)

C/C++

_O泡果奶_

// 最长上升子序列

#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)

4081littleprince

#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)

jtCrack

#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)

牛客126315号

最长递增子序列：
动态规划
dp[i] = max(dp[j]) + 1;
0<j<i&&num[i]>num[j]

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while(cin.hasNext()) {
            int n = cin.nextInt();
            int[] nums = new int[n];
            int[] dp = new int[n];
            for(int i=0; i<n; i++) {
                nums[i] = cin.nextInt();
            }
            
            dp[0]  = 1;
            int maxdp = 0;
            for(int i=1; i<n; i++) {
                int temp = 0;
                for(int j=0; j<i; j++) {
                    if(dp[j]>temp && nums[j]<nums[i]) {
                        temp = dp[j];
                        
                    }
                }
                dp[i] = temp + 1;
                if(dp[i] > maxdp) {
                    maxdp = dp[i];
                }
            }
            System.out.println(maxdp);
        }
    }
}

发表于 2016-03-27 10:58:31 回复(0)

Java

刷慢一点，各位

本质是求最长递增子序列，这题用动态规划即可，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)