2024年3月11日
习题 2.4 Repeater(北京大学复试上机题)
链接
题目大意
给你一个仅包含一种字符和空格的模板,模板显示如何创建无尽的图片,将字符用作基本元素并将它们放在正确的位置以形成更大的模板,然后不断进行该操作。
样例
输入:
3
# #
#
# #
1
3
# #
#
# #
3
4
OO
O O
O O
OO
2
0
输出:
# #
#
# #
# # # # # # # #
# # # #
# # # # # # # #
# # # #
# #
# # # #
# # # # # # # #
# # # #
# # # # # # # #
# # # #
# #
# # # #
# #
#
# #
# # # #
# #
# # # #
# # # # # # # #
# # # #
# # # # # # # #
# # # #
# #
# # # #
# # # # # # # #
# # # #
# # # # # # # #
OO OO
O OO O
O OO O
OO OO
OO OO
O O O O
O O O O
OO OO
OO OO
O O O O
O O O O
OO OO
OO OO
O OO O
O OO O
OO OO
解法
很显然,这里需要用到递归。其次,由于图形复杂,需要一个数字用来缓存图形,我们一点一点填进去。
大的绘图由小的模块组成,每个小的模块都可以再次拆分,直到每个小的模块只剩下单个字符,因此考虑使用递归。递归考虑为给定当前的模块的起始绘图区域,指定符号,交给下一个递归去绘制;空白,则直接绘制。
空白似乎也可以当作一种符号,没有必要分开处理
递归表达式:
d
r
a
w
(
d
e
p
t
h
,
x
,
y
)
=
{
a
n
s
[
x
+
i
]
[
y
+
j
]
=
t
e
p
[
i
]
[
j
]
(
d
e
p
t
h
=
=
1
)
d
r
a
w
(
d
e
p
t
h
−
1
,
x
+
i
∗
s
i
z
e
,
y
+
j
∗
s
i
z
e
)
(
d
e
p
t
h
>
1
)
\left. draw(depth,x,y)=\left\{\begin{aligned}&ans[x+i][y+j]=tep[i][j] &&(depth==1)\\&draw(depth-1,x+i*size,y+j*size) &&(depth >1)\end{aligned}\right.\right.
draw(depth,x,y)={ans[x+i][y+j]=tep[i][j]draw(depth−1,x+i∗size,y+j∗size)(depth==1)(depth>1)
其中,
i
,
j
∈
[
0
,
N
)
,
s
i
z
e
=
p
o
w
(
N
,
d
e
p
t
h
−
1
)
i,j\in [0,N),size=pow(N,depth-1)
i,j∈[0,N),size=pow(N,depth−1),
a
n
s
ans
ans 是目标图形,
t
e
p
tep
tep 是模板图形
代码
#include <iostream>
#include <cmath>
using namespace std;
int N, q;
char tep[3001][3001];
char ans[3001][3001];
void blank(int deep, int bx, int by) {
for (int i = 0; i < pow(N, deep); i ++ ) {
for (int j = 0; j < pow(N, deep); j ++ ) {
ans[bx+i][by+j] = ' ';
}
}
}
void pic(int bx, int by) {
for (int i = 0; i < N; i ++ ) {
for (int j = 0; j < N; j ++ ) {
ans[i+bx][j+by] = tep[i][j];
}
}
}
void help(int deep, int bx, int by) {
if (deep == 1) {
pic(bx, by);
return;
}
for (int i = 0; i < N; i ++ ) {
for (int j = 0; j < N; j ++ ) {
int nx = i * pow(N, deep-1);
int ny = j * pow(N, deep-1);
if (tep[i][j] == ' ') {
blank(deep-1, bx+nx, by+ny);
}
else {
help(deep-1, bx+nx, by+ny);
}
}
}
}
int main() {
while (cin >> N) { // 注意 while 处理多个 case
if (N == 0) break;
getchar();
for (int i = 0; i < N; i ++ ){
for (int j = 0; j < N; j ++ )
scanf("%c", &tep[i][j]);
getchar();
}
cin >> q;
help(q, 0, 0);
int size = pow(N, q);
for (int i = 0; i < size; i ++ ) {
for (int j = 0; j < size; j ++ ) {
printf("%c", ans[i][j]);
}
cout << '\n';
}
}
}
// 64 位输出请用 printf("%lld")
AcWing 动态规划 第一讲 数字三角形模型
基础
着重学习了 DP 的思考方式——基于集合的思考
计算顺序——拓扑序
方格取数
设有 N×N 的方格图,我们在其中的某些方格中填入正整数,而其它的方格中则放入数字0。如下图所示:
某人从图中的左上角 A 出发,可以向下行走,也可以向右行走,直到到达右下角的 B 点。
在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字0)。
此人从 A 点到 B 点共走了两次,试找出两条这样的路径,使得取得的数字和为最大。
输入格式
第一行为一个整数N,表示 N×N 的方格图。
接下来的每行有三个整数,第一个为行号数,第二个为列号数,第三个为在该行、该列上所放的数。
行和列编号从 11 开始。
一行“0 0 0”表示结束。
输出格式
输出一个整数,表示两条路径上取得的最大的和。
数据范围
N≤10
输入样例:
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
输出样例:
67
分析:
第一反应是两次 DP,但是经弹幕提醒,这样是不行的。这样属于贪心的思路,但是无法证明这样是对的,没有办法说明最优解是两个最大值的和(就好像一个集合最大值不能分解成两个子集的最大值的和)
正解是一次 DP:
核心问题:
- 走两次?—— 用一个状态统一,变成同时走
- 不能重复选?—— 体现在状态转移时,走到同一个点只做一次加法
状态表示:一个人分身,同时从起点出发走k步,分别走到(i1, k-i1), (i2, k-i2)时,路径数字之后的最大值。
状态转移:四种可能
代码
#include<iostream>
using namespace std;
const int N = 12;
int a[N][N], f[2*N][N][N];
int n;
int main(){
cin >> n;
int x, y, z;
while (cin >> x >> y >> z, x || y || z){
a[x][y] = z;
}
for (int k = 2; k <= n + n; k ++ )
for (int i1 = 1; i1 <= n; i1 ++ )
for (int i2 = 1; i2 <= n; i2 ++ ) {
int j1 = k - i1, j2 = k - i2;
if (j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n) {
int t = a[i1][j1];
if (i1 != i2) t += a[i2][j2];
int &x = f[k][i1][i2];
x = max(x, f[k-1][i1-1][i2-1] + t);
x = max(x, f[k-1][i1-1][i2] + t);
x = max(x, f[k-1][i1][i2-1] + t);
x = max(x, f[k-1][i1][i2] + t);
}
}
cout << f[n+n][n][n] << endl;
return 0;
}
要点
- 三维 DP,实质上利用了步数相同进行了降维。
- 输入中,while 的用法
- 循环从 k 开始,逻辑更加清晰,便于计算j1,j2
- 利用 t 表示两种情况
- 利用引用 x 简化代码
- 利用 4 个 max 函数求 4 种情况的最大值