洛谷 P1719 最大加权矩形 Java

题目描述

为了更好的备战 NOIP2013，电脑组的几个女孩子 LYQ,ZSC,ZHQ 认为，我们不光需要机房，我们还需要运动，于是就决定找校长申请一块电脑组的课余运动场地，听说她们都是电脑组的高手，校长没有马上答应他们，而是先给她们出了一道数学题，并且告诉她们：你们能获得的运动场地的面积就是你们能找到的这个最大的数字。

校长先给他们一个 N×N 矩阵。要求矩阵中最大加权矩形，即矩阵的每一个元素都有一权值，权值定义在整数集上。从中找一矩形，矩形大小无限制，是其中包含的所有元素的和最大 。矩阵的每个元素属于 [-127,127] ,例如

题目详细：洛谷P1719 最大加权矩形

思路：矩阵前缀和

题目的数据规模是n<=120,O(n⁴)完全可以。首先我们要会算矩阵的前缀和，也其实就是前缀和的变形。
a11 a12 a13 a14
a21 a22 a23 a24
a31 a32 a33 a34
a41 a42 a43 a44
左上顶点为a11，右下顶点为a33的矩阵的前缀和。
qz[3][3]=qz[2][3]+qz[3][2]-qz[2][2]
公式是qz[i][j]=qz[i-1][j]+qz[i][j-1]-qz[i-1][j-1]
为什么加上qz[6]呢，简单的容斥原理，大白话就是加多了减去一个。
qz[i]代表着以起始元素为左上顶点，以i这个点为右下顶点的矩形的全部和。

那么我们怎么利用矩阵前缀和算出任意一个矩阵的和呢，其实差不多的道理。还是那个矩阵，求a6、q7、a10、a11这个矩阵的和。
temp=qz[3][3]-qz[3][1]-qz[1][3]+qz[1][1]
求aij为左上顶点，amn为右下顶点的矩阵和。
公式是temp=qz[m][n]-qz[m][j-1]-qz[i-1][n]+qz[i-1][j-1]
a11 a12 a13 a14
a21 a22 a23 a24
a31 a32 a33 a34
a41 a42 a43 a44

然后遍历所有的矩阵，求出最大的那个就可以了，4个for循环解法。

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Main {
	public static void main(String[] args) throws IOException{
		StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter pw=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		in.nextToken();
		int N=(int)in.nval; 
		int[][] sum=new int[N+1][N+1];
		for(int i=1;i<=N;i++)
			for(int j=1;j<=N;j++)   //矩阵前缀和
			{
				in.nextToken();
				sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+(int)in.nval;
			}
		int temp,max=0x80000000;
		for(int i=1;i<=N;i++)
			for(int j=1;j<=N;j++)   
				for(int r=i;r<=N;r++)
					for(int b=j;b<=N;b++)
					{
						temp=sum[r][b]-sum[r][j-1]-sum[i-1][b]+sum[i-1][j-1];
						max=Math.max(max, temp);
					}
		pw.print(max);
		pw.flush();
	}
}