2023.05.31-暑期实习-第三题-太阳能发电板

TaZi SU @ 7 months ago

思路：二维前缀和

给定一个 $n*m$ 的矩阵，矩阵中的每个点，都有一个价值 $a[i][j]$ ，我们需要找到一个价值最大的矩阵，该矩阵的价值为其范围内所有点的价值之和，同时，每包含一个点，就需要减去 $5$ 的价值。

我们很容易想到，在直到矩阵大小后，我们能够 $O(1)$ 的计算出里面有多少个点，但是我们缺少一种方法，一种能够快速求得矩阵内价值总和的方法。

这种方法就是二维前缀和，它能够在 $O(NM)$ 的预处理后， $O(1)$ 获得我们想要的答案。

二位前缀和的原理如下：

假设我们有一个矩阵 $a$

定义：

$$a = \begin{Bmatrix} 0&1&2&3\\ 4&5&6&6\\ 8&9&10&11\\ 12&13&14&15 \end{Bmatrix} $$

$pre[i][j]$ 表示从左上角(1,1)到(i,j)的一个矩形的和，比如 $pre[2][2]=0+1+4+5=10$ 。

那么 $pre[i][j]$ 是怎么求来的呢？

我们在计算该数组时，从上往下，从左往右计算，那么当我们计算到 $pre[i][j]$ 时，它的左上一块矩阵的值就必定是已经计算好了。

好了，现在我们手上有以下三个数据 $pre[i-1][j],pre[i][j-1],pre[i-1][j-1]$ ，我们的目标是求出 $pre[i][j]$ 。

根据 $pre$ 数组的定义， $pre[i-1][j]$ 就是红＋绿， $pre[i][j-1]$ 就是红＋浅蓝，而 $pre[i-1][j-1]$ 就是红，于是我们可以很容易发现:

$pre[i][j] = pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+a[i][j]$

即：红+绿+红+浅蓝-红+蓝

这样我们就得到了一个 $pre$ 数组。当我们用 $pre$ 数组去求解我们需要的答案时，其实就是逆向的过程。这里不做讲解，留给读者自己理解。(可以想想，当我们拥有了 $pre$ 数组后，该如何求蓝色部分的值？)

代码

C++

#include <iostream>
#include <cstdio>
using namespace std;

bool matrix[15][15];
int m,n;
int ans=1e9;

bool check(int x,int y,int len){
	for(int i=0;i<len;++i){
		for(int j=0;j<len;++j){
			if(matrix[x+i][y+j]) return false;
		}
	}
	return true;
}

void fill(int x,int y,int len){// 采用异或方法进行填充/取消填充 
	for(int i=0;i<len;++i){
		for(int j=0;j<len;++j){
			matrix[x+i][y+j]^=1;
		}
	}
} 

void dfs(int x, int y, int cnt){
	if(cnt>=ans) return;// 剪枝，当前记录数已经≥已记录的最小答案，不再进行搜索
	if(x==m+1){// 填充完毕，更新答案 
		ans=cnt;
		return;
	}
	if(y>n) dfs(x+1,1,cnt);
	bool full=true;
	for(int i=y;i<=n;++i){// 从当前行的第y个格子开始枚举，找到第一个没有填充的格子 
		if(!matrix[x][i]){// 当前格子未填充，尝试填充正方形 
			full=false;
			for(int j=min(n-i+1,m-x+1);j>=1;--j){// 枚举填充正方形的边长，从长边开始枚举 
				if(check(x,i,j)){// 判断从第x行第i个格子开始能不能填充边长为j的长方形 
					fill(x,i,j);// 填充
					dfs(x,y+j,cnt+1);// 填充完一个正方形，尝试下一次填充
					fill(x,i,j);// 取消填充 
				}
			}
			break;// 尝试在当前格子填充正方形的所有情况已经全部考虑，直接弹出 
		}
	}
	if(full) dfs(x+1,1,cnt);// 当前行都填充了，搜索下一行 
}

int main(){
	scanf("%d %d",&m,&n);
	dfs(1,1,0);
	printf("%d",ans);
	
	return 0;
}

python

def check(x, y, length):
    # 判断从第x行第y个格子开始能否填充边长为length的正方形
    for i in range(length):
        for j in range(length):
            if matrix[x+i][y+j]:
                return False
    return True

def fill(x, y, length):
    # 采用异或方法进行填充/取消填充
    for i in range(length):
        for j in range(length):
            matrix[x+i][y+j] ^= 1

def dfs(x, y, cnt):
    global ans
    if cnt >= ans:
        return  # 剪枝，当前记录数已经≥已记录的最小答案，不再进行搜索
    if x == m + 1:
        ans = cnt  # 填充完毕，更新答案
        return
    if y > n:
        dfs(x + 1, 1, cnt)
    full = True
    for i in range(y, n + 1):
        # 从当前行的第y个格子开始枚举，找到第一个没有填充的格子
        if not matrix[x][i]:  # 当前格子未填充，尝试填充正方形
            full = False
            for j in range(min(n - i + 1, m - x + 1), 0, -1):
                # 枚举填充正方形的边长，从长边开始枚举
                if check(x, i, j):
                    fill(x, i, j)  # 填充
                    dfs(x, y + j, cnt + 1)  # 填充完一个正方形，尝试下一次填充
                    fill(x, i, j)  # 取消填充
            break  # 尝试在当前格子填充正方形的所有情况已经全部考虑，直接跳出循环
    if full:
        dfs(x + 1, 1, cnt)  # 当前行都填充了，搜索下一行

m, n = map(int, input().split())
matrix = [[False] * 15 for _ in range(15)]
ans = 1e9
dfs(1, 1, 0)
print(ans)

Java

import java.util.Scanner;

public class Main {
    static boolean[][] matrix = new boolean[15][15];
    static int m, n;
    static int ans = (int) 1e9;

    static boolean check(int x, int y, int len) {
        // 判断从第x行第y个格子开始能否填充边长为len的正方形
        for (int i = 0; i < len; ++i) {
            for (int j = 0; j < len; ++j) {
                if (matrix[x + i][y + j])
                    return false;
            }
        }
        return true;
    }

    static void fill(int x, int y, int len) {
        // 采用异或方法进行填充/取消填充
        for (int i = 0; i < len; ++i) {
            for (int j = 0; j < len; ++j) {
                matrix[x + i][y + j] ^= true;
            }
        }
    }

    static void dfs(int x, int y, int cnt) {
        if (cnt >= ans)
            return; // 剪枝，当前记录数已经≥已记录的最小答案，不再进行搜索
        if (x == m + 1) {
            ans = cnt; // 填充完毕，更新答案
            return;
        }
        if (y > n)
            dfs(x + 1, 1, cnt);
        boolean full = true;
        for (int i = y; i <= n; ++i) { // 从当前行的第y个格子开始枚举，找到第一个没有填充的格子
            if (!matrix[x][i]) { // 当前格子未填充，尝试填充正方形
                full = false;
                for (int j = Math.min(n - i + 1, m - x + 1); j >= 1; --j) { // 枚举填充正方形的边长，从长边开始枚举
                    if (check(x, i, j)) { // 判断从第x行第i个格子开始能不能填充边长为j的正方形
                        fill(x, i, j); // 填充
                        dfs(x, y + j, cnt + 1); // 填充完一个正方形，尝试下一次填充
                        fill(x, i, j); // 取消填充
                    }
                }
                break; // 尝试在当前格子填充正方形的所有情况已经全部考虑，直接跳出循环
            }
        }
        if (full)
            dfs(x + 1, 1, cnt); // 当前行都填充了，搜索下一行
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        m = scanner.nextInt();
        n = scanner.nextInt();
        dfs(1, 1, 0);
        System.out.println(ans);
        scanner.close();
    }
}

Go

package main

import "fmt"

var matrix [15][15]bool
var m, n int
var ans = int(1e9)

func check(x, y, length int) bool {
	// 判断从第x行第y个格子开始能否填充边长为length的正方形
	for i := 0; i < length; i++ {
		for j := 0; j < length; j++ {
			if matrix[x+i][y+j] {
				return false
			}
		}
	}
	return true
}

func fill(x, y, length int) {
	// 采用异或方法进行填充/取消填充
	for i := 0; i < length; i++ {
		for j := 0; j < length; j++ {
			matrix[x+i][y+j] = !matrix[x+i][y+j]
		}
	}
}

func dfs(x, y, cnt int) {
	if cnt >= ans {
		return // 剪枝，当前记录数已经≥已记录的最小答案，不再进行搜索
	}
	if x == m+1 {
		ans = cnt // 填充完毕，更新答案
		return
	}
	if y > n {
		dfs(x+1, 1, cnt)
	}
	full := true
	for i := y; i <= n; i++ {
		// 从当前行的第y个格子开始枚举，找到第一个没有填充的格子
		if !matrix[x][i] {
			 // 当前格子未填充，尝试填充正方形
			full = false
			for j := min(n-i+1, m-x+1); j >= 1; j-- {
				// 枚举填充正方形的边长，从长边开始枚举
				if check(x, i, j) {
					fill(x, i, j)         // 填充
					dfs(x, y+j, cnt+1)   // 填充完一个正方形，尝试下一次填充
					fill(x, i, j)         // 取消填充
				}
			}
			break // 尝试在当前格子填充正方形的所有情况已经全部考虑，直接跳出循环
		}
	}
	if full {
		dfs(x+1, 1, cnt) // 当前行都填充了，搜索下一行
	}
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	fmt.Scan(&m, &n)
	dfs(1, 1, 0)
	fmt.Println(ans)
}

Js

function check(x, y, length) {
  // 判断从第x行第y个格子开始能否填充边长为length的正方形
  for (let i = 0; i < length; i++) {
    for (let j = 0; j < length; j++) {
      if (matrix[x + i][y + j]) {
        return false;
      }
    }
  }
  return true;
}

function fill(x, y, length) {
  // 采用异或方法进行填充/取消填充
  for (let i = 0; i < length; i++) {
    for (let j = 0; j < length; j++) {
      matrix[x + i][y + j] = !matrix[x + i][y + j];
    }
  }
}

function dfs(x, y, cnt) {
  if (cnt >= ans) {
    return; // 剪枝，当前记录数已经≥已记录的最小答案，不再进行搜索
  }
  if (x === m + 1) {
    ans = cnt; // 填充完毕，更新答案
    return;
  }
  if (y > n) {
    dfs(x + 1, 1, cnt);
  }
  let full = true;
  for (let i = y; i <= n; i++) {
    // 从当前行的第y个格子开始枚举，找到第一个没有填充的格子
    if (!matrix[x][i]) {
      // 当前格子未填充，尝试填充正方形
      full = false;
      for (let j = Math.min(n - i + 1, m - x + 1); j >= 1; j--) {
        // 枚举填充正方形的边长，从长边开始枚举
        if (check(x, i, j)) {
          fill(x, i, j); // 填充
          dfs(x, y + j, cnt + 1); // 填充完一个正方形，尝试下一次填充
          fill(x, i, j); // 取消填充
        }
      }
      break; // 尝试在当前格子填充正方形的所有情况已经全部考虑，直接跳出循环
    }
  }
  if (full) {
    dfs(x + 1, 1, cnt); // 当前行都填充了，搜索下一行
  }
}

function main() {
  const readline = require("readline");
  const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
  });

  rl.on("line", (line) => {
    const input = line.split(" ").map(Number);
    m = input[0];
    n = input[1];
    rl.close();
  }).on("close", () => {
    matrix = new Array(15).fill(false).map(() => new Array(15).fill(false));
    dfs(1, 1, 0);
    console.log(ans);
    process.exit(0);
  });
}

main();

ID

Time

1000ms

Memory

256MiB

Difficulty

Tags

前缀和

# Submissions

Accepted

Uploaded By

TaZi

1 solutions

思路：二维前缀和

代码

C++

python

Java

Go

Js

Information

Status

Development

Support