Problem H: 方格取数
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 28 Solved: 9
Description
有N * N个格子,每个格子里有正数或者0,从最左上角往最右下角走,只能向下和向右,一共走两次(即从左上角走到右下角走两趟),把所有经过的格子的数加起来,求最大值SUM,且两次如果经过同一个格子,则最后总和SUM中该格子的计数只加一次。
Input
第一行N(1 <= N <= 100)
然后N行,每行N个数。依次表示N * N每个格子的数值。(0 <= value <= 1000) ;
Output
输出最大值SUM。
Sample Input
Sample Output
HINT
Hint
Possible Way:
第一次 1 -> 2 -> 2 -> 4 -> 2
第二次 1 -> 2 -> 3 -> 1 -> 2
SUM = 15
思路:
DP。一共走两次,可以看成两个人同时从起点走向终点。每个点都可以从上面或者左边得到,所以两个人同时走的话,可以有四种组合。故可以得到转移方程:
Dp [ X1 ] [ Y1 ] [ X2 ] [ Y2 ] = max (Dp [ X1 - 1 ] [ Y1 ] [ X2 - 1 ] [ Y2 ] ,
Dp [ X1 - 1 ] [ Y1 ] [ X2 ] [ Y2 - 1 ] ,
Dp [ X1 ] [ Y1 - 1 ] [ X2 - 1 ] [ Y2 ] ,
Dp [ X1 ] [ Y1 - 1 ] [ X2 ] [ Y2 - 1 ] )+ Map [ X1 ] [ Y1 ] + Map [ X2 ] [ Y2 ];
四个循环,范围为 1 ~ 100,那么时间复杂度 O(n ^ 4)会造成 TLE,所以还要进一步优化。用 k 代表步数,那么转移方程可以变为:
Dp [ k ] [ X1 ] [ X2 ] = max (Dp [ k - 1 ] [ X1 - 1 ] [ X2 - 1 ] ,
Dp [ k - 1 ] [ X1 - 1 ] [ X2 ] ,
Dp [ k - 1 ] [ X1 ] [ X2 - 1 ] ,
Dp [ k - 1 ] [ X1 ] [ X2 ] ) + Map [ X1 ] [ k - X1 ] + Map [ X2 ] [ k - X2 ];
这样的话时间复杂度降为 O (n ^ 3 )就不会导致TLE了。
如何避免走相同的格的时候只加一次呢?
因为 k 是一样的,说明当 x1 == x2 的时候,y1 == y2,这时候两个走在了同一格,所以只要判断是否 x1 == x2 就能决定要不要加两次了。若题目要求改为不允许走过同一点,将 x1 == x2 时候 continue 就可以了。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int dp[210][105][105]; int Map[105][105]; int main () { int n, sum; scanf("%d", &n); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) scanf("%d", &Map[i][j]); sum = n + n - 2; for (int k = 0; k <= sum; ++k) { for (int x1 = 0; x1 < n; ++x1) { for (int x2 = 0; x2 < n; ++x2) { int ans = 0; int y1 = k - x1, y2 = k - x2; if (k > 0 && x1 > 0 && x2 > 0) ans = max(ans, dp[k - 1][x1 - 1][x2 - 1]); if (k > 0 && x1 > 0 && y2 > 0) ans = max(ans, dp[k - 1][x1 - 1][x2]); if (k > 0 && y1 > 0 && x2 > 0) ans = max(ans, dp[k - 1][x1][x2 - 1]); if (k > 0 && y1 > 0 && y2 > 0) ans = max(ans, dp[k - 1][x1][x2]); if (y1 < 0 || y2 < 0) continue; dp[k][x1][x2] = ans + Map[x1][y1] + (x1 == x2 ? 0 : Map[x2][y2]); } } } printf("%d\n", dp[sum][n - 1][n - 1]); return 0; }
相关推荐
设有N*N的方格图(N≤10),我们在其中的某些方格中填入正整数,而其它的方格中则放入数字0。
里面有几个例题和解答,是一些比较老但是经典的题目,仅供参考
蓝桥杯VIP题和题解
位运算的讲解幻灯片,关于位运算的各种运用方式分析。
算法训练 方格取数 时间限制:1.0s 内存限制:256.0MB 问题描述 设有N*N的方格图(N),我们将其中的某些方格中填入正整数,
n*m方格数的计算n*m方格数的计算n*m方格数的计算n*m方格数的计算
如下的10个格子 +--+--+--+ | | | | +--+--+--+--+ ...一共有多少种可能的填数方案? 请填写表示方案数目的整数。 注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。 答案:1580
2013ACM集训队论文集.pdf
%根据计盒维数原理编写了求一维曲线分形维数的matlab程序 function D=FractalDim(y,cellmax) %求输入一维信号的计盒分形维数 %y是一维信号 %cellmax:方格子的最大边长,可以取2的偶数次幂次(1,2,4,8...),取大于数据...
90、1749数字方格(2020.03.13)a
最详细全面的黄金分割高精度计算算法资料,值得一看!(C/C++)
在软件设计实践课上关于方格旋转填数字的代码.通过循环嵌套解决问题
一个n * m的方格图,一些格子被涂成了黑色,在方格图中被标为1,白色格子标为0。问有多少个四连通的黑色格子连通块。四连通的黑色格子连通块指的是一片由黑色格子组成的区域,其中的每个黑色格子能通过四连通的走法...
骨牌铺方格及 代码骨牌铺方格及 代码骨牌铺方格及 代码
舒尔特方格android源码
舒尔特方格 (Schulte Grid) 是在一张方形卡片上画上 1cm*1cm 的 25 个方格,格子内任意填写上阿拉伯数字 1 ~ 25 等共 25 个数字。训练时,要求被测者用手指按 1 ~ 25 的顺序依次指出其位置,同时诵读出声,施测者一...
可简单快捷计算出场地方格网的土石方工程量
(Excel)方格网土石方计算表格
C#在窗体上动态生成小方格, 利用重载的方式取得窗体的的坐标,在相应的坐标描绘该点
本程序适合地形起伏不大的方形方格网法土方量计算,使用前请先在matlab中建立A矩阵并标定方格点的高程,比较适合大学生解决土方量计算时的繁琐计算。属于土木工程施工问题