数字三角形 Number Triangles(java的MLE解决办法)

2021-04-24 13:30

阅读:535

标签:ber   port   测试   src   input   long   包含   数字   alt   

题目链接:https://www.luogu.com.cn/problem/P1216

题目描述:

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

技术图片

 在上面的样例中,从 73875 的路径产生了最大

输入格式: 

第一个行一个正整数 rr ,表示行的数目。

后面每行为这个数字金字塔特定行包含的整数。

输出格式:

单独的一行,包含那个可能得到的最大的和。


解题思路 :

一道动态规划的题目,用java写了出来,代码如下,最后一个测试样例却是MLE,用C++写了一遍是通过的

import java.util.Scanner;
public class Main {
    static int max = 1001;
    static int dp[][] = new int[max][max];
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int r = cin.nextInt();
        
        for(int i=1;i) {
            for(int j=1;j) {
                int t = cin.nextInt();
                dp[i][j] = Math.max(dp[i-1][j-1],dp[i-1][j])+t;
            }
        }
        int ans = 0;
        for(int i=1;i) {
            ans = Math.max(ans, dp[r][i]);
        }
        System.out.println(ans);
    }
}

 技术图片

 于是在网上找相应的解决办法,如何对java的内存进行优化

 看到了一个大佬的博客:https://blog.csdn.net/hhczy1003/article/details/49854441

 于是使用了里面的IO读取加速的模板,套用了一下,就过了。。。

技术图片

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Scanner;
public class Main {
    static InputReader in;  
    static PrintWriter out; 
    static int dp[][] = new int[1001][1001];
    public static void main(String[] args) throws IOException {
        //Scanner cin = new Scanner(System.in);
        in = new InputReader(System.in);  
        out = new PrintWriter(System.out);
        int r = in.nextInt();
        int t;
        for(int i=1;i) {
            for(int j=1;j) {
                t = in.nextInt();
                dp[i][j] = Math.max(dp[i-1][j-1],dp[i-1][j])+t;
            }
        }
        int ans = 0;
        for(int i=1;i) {
            ans = Math.max(ans, dp[r][i]);
        }
        System.out.println(ans);
        out.close(); 
    }
    static class InputReader {  
        BufferedReader br;  
  
        public InputReader(InputStream stream) {  
            br = new BufferedReader(new InputStreamReader(stream));  
        }  
  
        public int nextInt() throws IOException {  
            int c = br.read();  
            while (c ) {  
                c = br.read();  
            }  
            boolean negative = false;  
            if (c == ‘-‘) {  
                negative = true;  
                c = br.read();  
            }  
            int x = 0;  
            while (c > 32) {  
                x = x * 10 + c - ‘0‘;  
                c = br.read();  
            }  
            return negative ? -x : x;  
        }  
  
        public long nextLong() throws IOException {  
            int c = br.read();  
            while (c ) {  
                c = br.read();  
            }  
            boolean negative = false;  
            if (c == ‘-‘) {  
                negative = true;  
                c = br.read();  
            }  
            long x = 0;  
            while (c > 32) {  
                x = x * 10 + c - ‘0‘;  
                c = br.read();  
            }  
            return negative ? -x : x;  
        }  
  
        public String next() throws IOException {
            int c = br.read();  
            while (c ) {  
                c = br.read();  
            }  
            StringBuilder sb = new StringBuilder();  
            while (c > 32) {  
                sb.append((char) c);  
                c = br.read();  
            }  
            return sb.toString();  
        }  
  
        public double nextDouble() throws IOException {  
            return Double.parseDouble(next());  
        }  
    }
}

 

数字三角形 Number Triangles(java的MLE解决办法)

标签:ber   port   测试   src   input   long   包含   数字   alt   

原文地址:https://www.cnblogs.com/123-wind/p/13262465.html


评论


亲,登录后才可以留言!