[原创]2017年第0届浙江工业大学之江学院程序设计竞赛决赛 B: qwb与矩阵
[原创]2017年第0届浙江工业大学之江学院程序设计竞赛决赛 B: qwb与矩阵
2017-06-03 01:43:28 Tabris_ 阅读数:924
博客爬取于2020-06-14 22:40:22
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72849513
题目链接:http://115.231.222.240:8081/JudgeOnline/problem.php?cid=1005&pid=1
———————————————————————————————————————
Problem B: qwb与矩阵
Time Limit: 2 Sec Memory Limit: 128 MB
Submit: 1030 Solved: 189
[Submit][Status][Web Board]
Description
做完了辣么多的数学题,qwb好好睡了一觉。但是他做了一个梦:
有一个n*m的矩阵,qwb在这个矩阵的左上角(1,1),终点在右下角(n,m)。
每个格子中有小钱钱,也可能没有,还有可能是要交过路费的,并且行走方向必须是靠近终点的方向。
往下走一次只能走一格,往右走一次可以走一格也可以走到当前列数的倍数格。
比如当前格子是(x,y),那么可以移动到(x+1,y),(x,y+1)或者(x,y*k),其中k>1。
qwb希望找到一种走法,使得到达右下角时他能够有最多的小钱钱。
你能帮助他吗?
Input
第一行是测试例数量 T (T<=100),接下来是T组测试数据。
每组测试数据的第一行是两个整数n,m,分别表示行数和列数(1<=n<=20,1<=m<=10000);
接下去给你一个n*m的矩阵,每个格子里有一个数字 k (-100<=k<=100)代表小钱钱的数量。 ∑nm<=3,000,000
Output
每组数据一行,输出L先生能够获得小钱钱的最大值(可能为负数)。
Sample Input
1
3 8
9 10 10 10 10 -10 10 10
10 -11 -1 0 2 11 10 -20
-11 -11 10 11 2 10 -10 -10
Sample Output
52
HINT
————————————————————————————————————————
很明显的dp
dp[i][j]为到(i,j)位置时的最大值.
转移方程大家都会,但是如果暴力可能会超时
所以在考虑走倍数的时候采用类似筛法的方法转移就好了
附本题代码
————————————————————————————————————————
1 | # include <bits/stdc++.h> |