首页 > 试题广场 >

Redraiment的走法

[编程题]Redraiment的走法

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

$\hspace{15pt}$ Redraiment 是走梅花桩的高手。现在，地上有 $n$ 个梅花桩排成一排，从前到后高度依次为 $h_1, h_2, \dots, h_n$ 。
$\hspace{15pt}$ Redraiment 可以任选一个梅花桩开始，向后跳到任意一个比当前高度高的梅花桩上。
$\hspace{15pt}$ 求 Redraiment 最多可以跳过多少个梅花桩。

输入描述:

第一行输入一个整数  代表梅花桩的数量。
第二行输入  个整数  代表每一个梅花桩的高度。

输出描述:

输出一个正整数，代表 Redraiment 最多可以跳过多少个梅花桩。

示例1

输入

6
2 5 1 5 4 5

输出

说明

在这个样例中，其中一个最优的选择是，从第一个桩子起跳，最多可以跳三个梅花桩，使用橙色加粗标识：。
另外一种最优选择是，从第三个桩子起跳，最多也可以跳三个梅花桩，使用橙色加粗标识：。

算法知识视频讲解

Java

牛客281381469号

经典动态规划问题，实际为求最长递增子序列问题（不要求连续），dp[i]含义为以下标i结尾的最长递增子序列。
把dp数组初始化为1，因为以每个数结尾的最长递增子序列至少为其本身。
两层for循环，外层i由1到结尾，内层j由0到i，如果map[i] > map[j]，dp[i] = Math.max(dp[i], dp[j] + 1)，
时刻保存dp[i]的最值max，因为最长递增子序列不一定以最后一个元素为结尾！最后输出max即可。
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int[] dp = new int[n];
            int[] map = new int[n];
            for (int i = 0; i < n; i++){
                map[i] = in.nextInt();
            }
            Arrays.fill(dp, 1);
            int max = 1;
            for (int i = 1; i < n; i++){
                for (int j = 0; j < i; j++){
                    if (map[i] > map[j]){
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                        max = Math.max(dp[i], max);
                    }
                }
            }
            System.out.println(max);
        }
    }
}

发表于 2025-07-20 23:47:28 回复(0)

Java

牛客160935469号

import java.util.Scanner;

// 每个位置除去若干奇点的最长正序子串（动态规划）
// 如果从左往右数，那就从右往左循环，反之亦然（不然无法利用之前所得的结果）
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] h = new int[n];
        for (int i = 0; i < n; i++) {
            h[i] = in.nextInt();
        }
        int max = 0;
        int[] dp = new int[n];
        for (int i = n - 2; i >= 0; i--) {
            int curr = -1;
            for (int j = i + 1; j < n; j++) {
                if (h[j] > h[i] && dp[j] > curr) {
                    curr = dp[j];
                    dp[i] = dp[j] + 1;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            max = max > dp[i] ? max: dp[i];
        }
        System.out.println(max+1);
    }
}

发表于 2024-10-04 09:45:03 回复(0)

Java

GCID

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=in.nextInt();
        }
        int max=0;
        int[] DP=new int[n];
        for(int i=0;i<n;i++){
            DP[i]=1;
            for(int j=0;j<i;j++){
                if(arr[i]>arr[j]){
                    DP[i]=Math.max(DP[i],DP[j]+1);
                }
            }
            max=Math.max(max,DP[i]);
        }
        System.out.println(max);
    }
}

发表于 2023-09-09 21:13:02 回复(0)

Java

Hubert_D

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String[] str = null;
        while (sc.hasNext()) {
            sc.nextLine();
            str = sc.nextLine().split(" ");
        }
        /*int[] intChar = Arrays.stream(str)//通过流来处理str
                .mapToInt(Integer::parseInt).
                toArray();
                //流处理方法,忘得差不多了,不看了就先,先做题在说
*/
        int[] hight = new int[str.length];//定义一个数组存放梅花桩高度
        for (int i = 0; i < str.length; i++) {
            hight[i] = Integer.parseInt(str[i]);
        }
        //定义一个数组用来存放在以第i个桩为终点时,前面的最长递增子序列
        int[] num = new int[hight.length];
        Arrays.fill(num, 1);//用1初始化num数组
        for (int i = 1; i < hight.length; i++) {//i代表以i为终点也能以0为起点开始算终点,但是意义
            for (int j = 0; j < i; j++) {//j代表i前面的任意点,那么num[j]就是当前
                //从0开始计算,如果j比i低了,那么就代表i多了个解法
                //i的最大上升子序列是在自己前面,比自己低的点的最大上升子序列+1
                if ((hight[i] > hight[j])//如果i点位置比j高,
                        && (num[j] >= num[i])) //并且此时记录的j点的最大步数多于或等于此时记录的i点的最大步数
                    num[i] = num[j] + 1;
            }


        }
        Arrays.sort(num);
        System.out.println(num[num.length-1]);//没有注释的代码就是依托带边,我**自己都看不懂

    }

编辑于 2023-02-24 16:44:05 回复(0)

Java

陈一月的编程岁月

动态规划求最长递增子序列

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 获取输入的梅花桩个数
        int n = in.nextInt();
        // 定义一个数组，用于存放梅花桩的高度
        int[] hight = new int[n];
        // 获取输入的梅花桩高度
        for (int i = 0; i < n; i++) {
            hight[i] = in.nextInt();
        }
        // 定义一个数组，用于存放第i个梅花桩时，前面可生成的递增最长子序列个数
        int[] dp = new int[n];
        // 将dp最长默认全部赋值为1
        Arrays.fill(dp, 1);
        // 定义一个变量，表示第i个木桩前面的最长递增子序列个数,默认为1个,及求dp数组中的最大值
        int max = 1;
        // 利用动态规划求第i个木桩的最长递增子序列，最需要求得第i个木桩最长的递增子序列后加上1就OK
        for (int i = 1 ; i < n; i++) {
            for (int j = 0 ; j < i; j++) {
                if (hight[i] > hight[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(dp[i], max);
        }
        // 输出结果
        System.out.println(max);
    }
}

发表于 2023-02-14 10:04:08 回复(0)

Java

cui牛

//        6
//        2 5 1 5 4 5
//        0 1 2 3 4 5
//        dp[i] 表示以i为结尾的最长子序列的长度


//      当只有一个元素  [2]
//                  dp[0]=1


//      加入元素5 ,[2,5]
//      dp[0]=1  ,d[1]=d[0]+1=2  5比2大,所以可以在2的基础上加


//      加入元素1 ,[2,5,1]
//      dp[0]=1  ,d[1]=2   d[2]=1

//      加入元素5 ,[2,5,1,5]
//      dp[0]=1  ,d[1]=2   d[2]=1, d[3]=max{d[0]+1,d[2]+1}=2

//      加入元素4 ,[2,5,1,5,4]
//      dp[0]=1  ,d[1]=2   d[2]=1, d[3]=2, d4=max{d[0]+1,d[2]+1,}=2

//      加入元素5 ,[2,5,1,5,4,5]
//      dp[0]=1  ,d[1]=2   d[2]=1, d[3]=2, d[4]=2,d5=max{d[0]+1,d[2]+1,d[4]+1}=3
//        dp[0]=1  ,d[1]=2   d[2]=1, d[3]=2, d[4]=2,d[5]=3


    }

发表于 2023-02-03 10:57:19 回复(1)

Java

炮炮小明

import java.util.Arrays;
import java.util.Scanner;

public class HJ103_dp最长增子序列 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] high=new int[n];
        int[] dp=new int[n];
        Arrays.fill(dp, 1);
        for (int i = 0; i <n; i++) {
            high[i]=sc.nextInt();
        }
        int max = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if(high[j]<high[i]){
                    dp[i]= Math.max(dp[i],dp[j]+1);
                    max=Math.max(dp[i],max);
                }
            }
        }
        System.out.println(max);
    }
}

发表于 2022-08-26 15:38:37 回复(0)

Java

Cyan_Mu

带注释版的动态规划和二分法两种方法

/**
 * @author YXQ
 * @create 2022/8/25  15:04
 */

import java.util.Arrays;
import java.util.Scanner;

/**
 * Redraiment是走梅花桩的高手。Redraiment可以选择任意一个起点，从前到后，但只能从低处往高处的桩子走。他希望走的步数最多，你能替Redraiment研究他最多走的步数吗？
 * 输入描述：
 * 数据共2行，第1行先输入数组的个数，第2行再输入梅花桩的高度
 * 输出描述：
 * 输出一个结果
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        for (int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
//        System.out.println(findRedraiment(n,arr));
        System.out.println(find(n,arr));
    }
//    方法2.二分+贪心 dp[i]数组用来存长度为i+1的尽可能小的值
//    *****但是注意 这个dp数组并不是走的路径（因为会存在从右向左走的情况），但是长度和路径长度一样
    public static int find(int n,int[] arr){
        int[] dp=new int[n];
        dp[0]=arr[0];
        int index=0;
        for (int i=1;i<n;i++){
//            如果arr[i]大于dp中最大的值，则直接在dp后面加一位
            if(dp[index]<arr[i])dp[++index]=arr[i];
//            如果arr[i]<=dp[len],则替换掉第一个大于等于arr[i]的数  利用二分法在dp中找到这个数
//            左闭右开型的二分法
            else{
                int l=0,r=index;
                while (l<r){
                    int mid=l+(r-l)/2;
                    if(dp[mid]>=arr[i])r=mid;
                    else l=mid+1;
                }
                dp[r]=arr[i];
            }
            System.out.println();
        }
        return index+1;
    }
//    方法1.直接动态规划
    public static int findRedraiment(int n,int[] arr){
        int[] dp=new int[n];
        int res=0;
        Arrays.fill(dp,1);
        for (int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(arr[j]<arr[i])dp[i]=Math.max(dp[i],dp[j]+1);
                if(dp[i]>res)res=dp[i];
            }
        }
        return res;
    }
}

发表于 2022-08-25 16:39:40 回复(0)

Java

牛客200498065号

发表于 2022-08-13 22:13:45 回复(0)

Java

人流如织

最长递增子序列

发表于 2022-06-17 10:05:33 回复(0)

Java

琦琦爸爸

这个测试

73 58 213 78 255 231 165 52 51 288 93 177 61 270 116

预期输出是5步怎么算出来的感觉单元测试错了啊

发表于 2022-05-24 22:36:21 回复(0)

Java

牛客665016343号

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str =null;
        String s =null;
        while((s=br.readLine())!=null){
            str=br.readLine();
            System.out.println(dealString(str));
        }
    }
    public static int dealString(String str){
        ArrayList<Integer> al = new ArrayList();
        
        int max=0;
        String[] strs= str.split(" ");
        for(int i = 0;i < strs.length;i++){
            al.add(Integer.parseInt(strs[i]));
        }
        int[] dp = new int[al.size()];
         for(int i = 0;i < al.size();i++){
             dp[i] =1;
             for(int j = 0;j<i;j++){
                 if(al.get(i)>al.get(j)){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                 }
                     
             }
        }
        for(int i = 0 ; i < dp.length;i++){
            if(dp[i]>max){
                max = dp[i];
            }
        }
        return max;
    }
}

发表于 2022-05-04 21:49:56 回复(0)

Java

米斯特rollin

使用两个下标i,j（j<i）计算数组arr 与对应dp的值；如果arr[i] > arr[j] 的时候；计算dp[i] 此时 dp[i] = Math.max(dp[i], dp[j]+1)；

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int[] dp = new int[n];
        Arrays.fill(dp, 1); // 初始化为1
        int max = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // 当前的值比前面的值大的时候需要计算。
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    max = Math.max(dp[i], max);
                }
            }
        }
        System.out.println(max);
    }
}

发表于 2022-05-03 18:13:06 回复(0)

Java

牛客chow

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = sc.nextInt();
            }
            count(arr);
        }
    }
    private static void count(int[] arr) {
        int[] countArr = new int[arr.length];
        Arrays.fill(countArr, 1);
        int max = 1;
        // 以索引1结尾，求最长子序列，存入countArr[1]
        // 当以2结尾时，就可以取1的最长子序列作为参考(这就是动态规划的核心-取前面的累计值作为参考)
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    // countArr[j]表示目前截止j处最长子序列，那么countArr[i]最长就是countArr[j]，
                    // 而arr[j] < arr[i]，那么countArr[i]就+1，反之countArr[i]不变
                    countArr[i] = Math.max(countArr[j] + 1, countArr[i]);
                }
                max = Math.max(max, countArr[i]);
            }
        }
        System.out.println(max);
    }
}

发表于 2022-04-09 19:52:52 回复(0)

Java

阳怀弘晴

// 动态规划

import java.util.*;

public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int sum = sc.nextInt();
int[] num = new int[sum];
for(int i=0;i<sum;i++){
num[i] = sc.nextInt();
}
int[] dp = new int[sum];
Arrays.fill(dp,1);
for(int i=1;i<sum;i++){
for(int j=0;j<i;j++){
if(num[j]<num[i]) dp[i] = Math.max(dp[i],dp[j]+1);
}
}
int max = 1;
for(int i:dp){
max = Math.max(max,i);
}
System.out.println(max);
}
}

发表于 2022-04-09 17:08:24 回复(0)

Java

wwwzzz

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int cnt = in.nextInt();
            int[] arr = new int[cnt];
            for (int i = 0; i < cnt ; i++) {
                arr[i] = in.nextInt();
            }
            int a = maxLen2(arr);
            System.out.println(a);
        }
    }
    
    private static int maxLen2(int[] arr) {
        int len = arr.length;
        int[] dp = new int[len];
        int max = 0;
        for (int i = 0; i < len; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        
        for (int i = 1; i < len; i++) {
            max = Math.max(max, dp[i]);
        }
        return max;
    }
    
    private static int maxLen(int[] arr) {
        int len = arr.length;
        int[] dp = new int[len+1];
        dp[0] = 0;
        int di = -1;
        int dj = -1;
        for (int i = 0; i < len; i++) {
            di = i + 1;
            dp[di] = 1;
            for (int j = 0; j < i; j++) {
                dj = j + 1;
                if (arr[i] > arr[j]) {
                    dp[di] = Math.max(dp[di], dp[dj] + 1);
                }
            }
        }
        int max = 0;
        for (int i = 1; i <= len; i++) {
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

发表于 2022-03-21 23:38:52 回复(0)

Java

_nohave

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] arr = new int[n];
        for(int i = 0;i < n;i++){
            arr[i] = scan.nextInt();
        }
        
        int x = -1;
        for (int i = 0; i < n; i++) {
            int m = returnStep(arr, i);
            if (m > x) {
                x = m;
            }
        }
        System.out.println(x);
    }

    public static int returnStep(int[] arr, int index) {
        //{3,65,7,67,8,9,4,1,5,8,9} 1
        int start = index;
        int res = -1;
        while (start < arr.length){
            int count = 1;
            int x = arr[index];
            for (int i = start; i < arr.length; i++) {
                if(arr[i] > x){
                    x = arr[i];
                    count ++;
                }
            }
            start ++;
            if(count > res){
                res = count;
            }
        }
        //System.out.println(res);
        return res;
    }
}

为什么我的只通过了 3/20,我想while循环来确定每一轮中最大的升序,main函数中的

for循环控制走多少轮,第一轮从index = 0开始,依次递增调用returnStep()返回概论中

的最大子升序

发表于 2022-03-14 17:23:39 回复(0)

Java

牛客286918393号

// 这里的思路和24题合唱团一样

import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while(scan.hasNext()) {
int len = scan.nextInt();
int[] arrs = new int[len];
int[] rightNum = new int[len];
for(int i=0; i<len; ++i) {
arrs[i] = scan.nextInt();
rightNum[i] = 1;
}

for(int i=len-1; i>=0; --i) {
for(int j=len-1; j>i; --j) {
if((arrs[i] < arrs[j]) && (rightNum[i]< rightNum[j]+1)) {
rightNum[i] = rightNum[j] + 1;
}
}
}
// 从递增数组中获取最大值
int max = 0;
for(int val : rightNum) {
if(max < val) {
max = val;
}
}

      System.out.println(max);
}

      scan.close();
}
}

发表于 2022-02-23 11:06:53 回复(0)