JAVA编程(动态规划)——POJ1050

/*
* Author: poj_whut_shz
* Problem: Radar Installation
* Code: poj_1050
* URL: http://poj.org/problem?id=1050
* Data: 2019/9/9
*/
/*
*
【题意分析】：
*
给定一个N*N的矩阵，在矩阵中寻找一个h*w的矩阵，
*
使得对于所有可能的矩阵，这个矩阵的所有元素和最大，
*
并输出这个最大值。
*
*
【解题思路】：
*
该题可以转换为一维数组的最大字段和问题。
*
转换的关键就是，对于同一列，在保证上下连续的情况下按照不同的方式求和，
*
然后将同一种求和方式排成一行，对这一行求取最大子序列和，
*
并遍历完所有的求和方式。
*
*
【关于最大字段和问题】：
*
由于我在学习过程中接触到的只有分治法求解最大字段和问题，对此也特意查询了资料。
*
*
1、如果不会算法，使用枚举，i为从1到n的起点，
*
j为从i到n的终点，k为从i到j的子段之和。 时间复杂度为O(n^3)。
*
*
2、还是枚举，改进一下，就是将k去掉，在找其终点j的时候就将子段和记录下来，
*
因为从i到j的子段和就是从i到j-1的子段和加上a[j]。 时间复杂度为O(n^2)。
*
*
3、分治算法：这个序列分成1到(1+n)/2的序列与(1+n)/2到n的序列。
*
那么最大的子段有可能出现在： 左侧序列、右侧序列和跨越中间点的序列。
*
从中间点两侧找最大子段，再找越过中间点的最大子段，复杂度为O(nlogn)的算法。
*
*
4、动态规划：在选择一个元素a[j]的时候，只有两种情况，将a[i]至a[j-1]加上，
*
或者从a[j]以j为起点开始。用一个数组dp[i]表示以i为结束的最大子段和，
*
对于每一个a[i]，加上dp[i-1]成为子段，或以a[i]开始成为新段的起点。
*
因为只需要记录dp值，所以复杂度是O(n)。
*/
package dp;
import java.util.Scanner;
public class P1050 {
private static int[][] sum; //s(i,j)代表以第i行第j个元素为起始，垂直长度为row+1的列的和。
private static int[][] arr; //存储二维数组
private static int n; //存储二维数组的边长
private static int totalMax = -12800; //存储最终结果
private static void findMax() {
int[] rowP = new int[n]; //动态规划序列
int[] rowA = new int[n]; //放置当前操作行
for(int row = 0; row < n; row++) {
for(int i = 0; i < (n - row); i++) {
rowA = arr[row+i];
for (int j = 0; j < n; j++){
sum[row][j] += rowA[j];
}
rowP[0]=sum[row][0];
//问题转化成，在这个行中，求最大字段和的问题
for (int j = 1; j < n; j++){
//一维最大子序列和的问题
if (rowP[j - 1] < 0){
rowP[j] = sum[row][j];
}
else{
rowP[j] = rowP[j - 1] + sum[row][j];
}
}
int max = -12800;
for (int j = 0; j < n; j++){
if (rowP[j] > max) {
max = rowP[j]; //求出的max就是在垂直长度为row+1的所有矩形中，矩形内元素和的最大值
}
}
if (totalMax < max) {
totalMax = max; //最终结果
}
}
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
arr = new int[n][n];
sum = new int[n][n];
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
arr[i][j] = scan.nextInt();
}
}
findMax();
System.out.println(totalMax);
scan.close();
}
}

最后

以上就是执着季节为你收集整理的JAVA编程(动态规划)——POJ1050的全部内容，希望文章能够帮你解决JAVA编程(动态规划)——POJ1050所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。