D
原题链接
大意
n*n正方形 有黑有白
每次可以选择一个 矩形把它全变成白色，代价是max(长,宽)
求吧 整个正方形 全变白 的最小代价
数据范围
n <= 50
题解
首先如果 我们刷了两个有相邻边或重叠的 白色矩形
那么 假设他们的代价分别为 x和y
那么 一定有 一个 变长为x+y的正方形 完全覆盖了这两个白色矩形
dis|row| <= rowX+roxY <= costX+costY = x+y
dis|col| <= colX+roxY <= costX+costY = x+y
所以综上所述 两两不重叠
再来，证明 如果 最优结果要么选择的单一矩形，要么一定能 垂直 或水平分化,即是 不会出现类似 弦图 这样的分化
假设存在，那么意味这有n*m的矩形，和对应选择多个图画方案，使得
- 图画方案是最优的
- 子选择矩形个数大于1
- 不存在按竖着 分化,或横着分化，使得子选择被分开
对于横向来看，意味着任意选择分割线 都会和最优解的选择中的矩形的横着的边冲突，
也就意味着，从min横向点 到 max横向点，所有点都有边。
即是，从横向看 最优解的 cost 横向 >= (max横向点-min横向点)
由对称性，从纵向看 最优解的 cost 纵向 >= (max纵向-min纵向点)
那么我们直接用 相应的大矩形(max横向点-min横向点,max纵向-min纵向点) 从面积上覆盖 最优解答
即
大矩形 cost (从覆盖关系，和最优解答定义)>= 最优解答cost (根据横向和纵向边的关系)>= 大矩形cost
综上
- 没有重叠 至多相邻
- 要么 单一选择的矩形(如大矩形)，要么可纵向 或 可横向分割
所以
1
2
3
4
5
6
| dp[top i0 -> bottom i1][left j0 -> right j1]
=min(
max(i1-i0,j1-j0),
dp[i0 -> k][j0->j1] + dp[k+1->i1][j0->j1],
dp[i0 -> i1][j0 -> k] + dp[i0->i1][k+1->j1],
)
|
时间复杂度 O(枚举长 * 枚举宽 * 枚举左上角坐标 * 状态转移) = O(n * n * (n * n) * n) = O(n^5)
能过
代码 Rust
920ms/1s 强行 过了,慢应该是用Vec的原因,如果换成c++的直接数组的话，应该能快很多，// 我暂时还没玩会Rust的多维数组
CODE URL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #![allow(unused_imports)]
use std::cmp::*;
use std::collections::*;
struct Scanner {
buffer : std::collections::VecDeque<String>
}
impl Scanner {
fn new() -> Scanner {
Scanner {
buffer: std::collections::VecDeque::new()
}
}
fn next<T : std::str::FromStr >(&mut self) -> T {
if self.buffer.len() == 0 {
let mut input = String::new();
std::io::stdin().read_line(&mut input).ok();
for word in input.split_whitespace() {
self.buffer.push_back(word.to_string())
}
}
let front = self.buffer.pop_front().unwrap();
front.parse::<T>().ok().unwrap()
}
}
fn main() {
let mut s = Scanner::new();
let n : usize = s.next();
let mut dp = vec![vec![vec![vec![0;n+1];n+1];n+1];n+1];
for i in 0..n {
let line:String = s.next();
for (j, ch) in line.chars().enumerate() {
if ch == '#' {
dp[i][j][i][j] = 1;
}
}
}
for i in 0..n {
for j in 0..n {
if i == 0 && j == 0 {
continue;
}
for p in 0..n-i {
for q in 0..n-j {
let (x,y) = (i+p,j+q);
dp[p][q][x][y] = max(i,j)+1;
for k in p..x {
dp[p][q][x][y]=min(dp[p][q][x][y],dp[p][q][k][y]+dp[k+1][q][x][y]);
}
for k in q..y {
dp[p][q][x][y]=min(dp[p][q][x][y],dp[p][q][x][k]+dp[p][k+1][x][y]);
}
}
}
}
}
println!("{}",dp[0][0][n-1][n-1]);
}
|