求助站外题
  • 板块题目总版
  • 楼主william_zy
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/8/5 13:30
  • 上次更新2023/11/4 11:56:33
查看原帖
求助站外题
201971
william_zy楼主2021/8/5 13:30

求助一道题目:

【题目描述】
有一个H行W列的棋盘第i行第j列的棋盘格记为(i,j)。每个格子中都写了两个数,(i,j)中写有整数 $A_ij$ 和Bij。
高桥君首先对每个格子里的两个数染色:一个涂成红色,另一个涂成蓝色。
染色完成后,高桥君从左上角(1,1)出发,每次可以向左或向下走一格,直到到达右下角(H,W)。途中经过的所有格子(包括起点和终点)中红色数字之和记为R,蓝色数字之和记为B。
通过适当的染色以及选取合适的路径,高桥君想要R和B之差的绝对值尽可能的小。问∣R−B∣的最小值是多少?
【输入格式】
输入共2H+1行
第1行,两个正整数H,W
第2到H+1行,每行W个整数,第i+1行第j个数为Aij
第H+22H+1行,每行W个整数,第i+H+1行第j个数为Bij 
【输出格式】
输出∣R−B∣的最小值
【输入样例#12 2
1 2
3 4
3 4
2 1
【输出样例#10
【输入样例#22 3
1 10 80
80 10 1
1 2 3
4 5 6
【输出样例#22
【样例#1说明】
如下图染色和选择路径,路上红色数总和R=3+3+1=7,蓝色数总和B=1+2+4=7,所以∣R−B∣的最小值是0。

【数据说明】
2≤H,W≤80
0≤Aij,Bij
 ≤80

DPDP 的状态转移方程

2021/8/5 13:30
加载中...