`
水木清华77
  • 浏览: 36882 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

Problem18/Problem67

阅读更多
package com.yao.Algorithms;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.Reader;

/**
 * 
 * @author shuimuqinghua77 @date 2011-12-4
 * 
 */
public class Problem18 {
	private final static int SIZE = 100;

	public static void main(String[] args) throws Exception {
		/***
		 * 打开文件triangle.txt 内容如下
		 * 
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
		 */
		File file = new File("C:\\Users\\Administrator\\Desktop\\triangle.txt");
		Reader in = new FileReader(file);
		BufferedReader br = new BufferedReader(in);
/***
 * 把文件里面的内容读到数组arr中
 */
		int[][] arr = new int[SIZE][SIZE];
		int lineNum = 0;
		do {
			String line = br.readLine();
			if (line == null)
				break;
			line = line.trim();
			String[] str = line.split(" ");
			for (int j = 0; j < str.length; j++) {
				arr[lineNum][j] = Integer.parseInt(str[j]);
			}
			lineNum++;
		} while (true);
		br.close();
		in.close();
	/**
	 * 动态规划
	 * 问题Problem18转化求点S(顶点)到 点F(最底端的SIZE个节点)的最大距离中的最大值,
	 * 点A到点B的最大距离,就是点A到点B的父节点(B点有2个父节点)的最大距离+父节点到B的距离。题目转化为层层推进,即一层一层求解
	 */
		int[] premax = new int[SIZE];/**依次存放每一层中的点到顶点的最大值*/
		for (int k = 0; k < SIZE; k++) {
			int[] max = new int[SIZE];
			for (int m = 0; m <= k; m++) {
				if (m == 0)
					max[m] = arr[k][m] + premax[m];
				else {
					max[m] = premax[m] > premax[m - 1] ? arr[k][m] + premax[m]
							: arr[k][m] + premax[m - 1];
				}
			}
			premax = max;
		}
		int result = 0;
		for (int mm : premax) {
			if (mm > result)
				result = mm;
		}
		System.out.println(result);
		

	}

}
分享到:
评论

相关推荐

    https://www.luogu.com.cn/problem/solution/P8595

    https://www.luogu.com.cn/problem/P8595 https://www.luogu.com.cn/problem/P8595 https://www.luogu.com.cn/problem/P8595 https://www.luogu.com.cn/problem/P8595 https://www.luogu.com.cn/problem/P8595 ...

    maven3 + jetty 新建webapp

    标题 "maven3 + jetty 新建webapp" 涉及到的是使用Apache Maven 3构建工具和Jetty轻量级应用服务器来创建一个新的Web应用程序的过程。在Java开发领域,Maven是广泛使用的项目管理和集成工具,它帮助管理项目的构建、...

    acm新手刷题攻略之poj

    ### ACM新手刷题攻略之POJ ... - 推荐题目:[poj1068](https://vjudge.net/problem/POJ-1068)、[poj2632](https://vjudge.net/problem/POJ-2632)、[poj1573](https://vjudge.net/problem/POJ-1573)、[poj2993]...

    集装箱装载问题的 混合遗传 算法_python_代码_下载

    https://github.com/Nivedha-Ramesh/Container-Loading-Problem/blob/master/True%20Solution.png https://github.com/Nivedha-Ramesh/Container-Loading-Problem/blob/master/Fitness%20Variation.png ...

    Problem Solving with C++, 10th Global Edition

    Problem Solving with C++, Global Edition by Walter Savitch (author) (Author) Pages:1117 出版社: Pearson Education Limited; 10th edition edition (November 20, 2017) Language: English ISBN-10: ...

    Computer-Based.Problem.Solving.Process

    Chapter 18. Batch Operating System Chapter 19. Problem of Protection Chapter 20. Timing Program Execution Chapter 21. Efficiency of Batch Operating Systems Chapter 22. Convenience of the BOS Chapter ...

    problem-spring-web, 在 spring Web MVC中,处理问题的库.zip

    problem-spring-web, 在 spring Web MVC中,处理问题的库 Web站点MVC问题 问题 spring 是一个库,它使得从 spring 应用程序中生成 application/problem json 响应变得容易。 工具填补了一个利基,它将问题库和mvc...

    leetcode答案-leetcode:https://leetcode.com/problemset/algorithms/上的答案

    leetcode 答案leetcode 回答

    node-problem-detector-0.8.7.tar

    node-problem-detector 镜像包 v0.8.7 版本

    Wicked Problem

    ### Wicked Problem与Wicked Environmental Problem #### 一、引言 "Wicked Problem"(棘手问题)这一概念最初由霍恩(Horst Rittel)和韦伯(Melvin Webber)于1973年提出,指的是那些复杂且难以解决的问题。这类...

    problem

    标题 "problem" 提供的信息较少,但从描述中的 "NULL 博文链接:https://eric0000.iteye.com/blog/322311" 可以推测,这可能是一个关于解决某个问题或者技术讨论的博客文章链接。由于没有具体的博文内容,我们无法...

    MCM 2012 problem A B C 论文

    MCM 2012年 problem A problem B problem C 枪手论文

    《Approaching (Almost) Any Machine Learning Problem》

    Approaching (Almost) Any Machine Learning Problem是一本旨在帮助读者掌握机器学习问题解决方法的书籍。这本书涵盖了机器学习的基本概念、模型选择、数据预处理、特征工程、模型评估等多方面的知识点。 机器学习...

    CodeForces-Div.2A

    Codeforces部门2,A # And a2oj Ladder 4 some problems Ladder URL:http://a2oj.com/Ladder.jsp?ID=4难度等级:2问题提示: 1- 4A. Watermelon: ...

    Problem Solving with C++(9th) 无水印pdf

    Problem Solving with C++(9th) 英文无水印pdf 第9版 pdf所有页面使用FoxitReader和PDF-XChangeViewer测试都可以打开 本资源转载自网络,如有侵权,请联系上传者或csdn删除 本资源转载自网络,如有侵权,请...

    Problem_C_Data.zip

    "Problem_C_Data.zip" 是一个压缩包文件,包含2020年美国数学建模竞赛(简称美赛)C题的题目及相应的原始数据。美赛是一项国际性的数学建模竞赛,每年吸引众多学生参与,旨在提升参赛者的数学、数据分析和解决实际...

    Problem Arrangement zoj 3777

    Problem Arrangement zoj 3777

    machine problem

    在操作系统课程中,"机器问题"(Machine Problem)通常指的是与计算机硬件、系统架构以及操作系统内核相关的复杂问题。这些问题涉及到资源管理、并发控制、进程调度、内存分配等多个核心概念,是理解操作系统工作...

    算法设计taxi problem

    算法设计里关于taxi problem的C语言代码

Global site tag (gtag.js) - Google Analytics