[原创]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
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
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

inline int read(){
int x=0,f=1;char ch=getchar();
while('0'>ch||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
/**************************************/

int n,m;
int a[22][11111];
int dp[22][11111];

int main(){
int _=read();
while(_--){
n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]=read(),dp[i][j]=-2000000000;

dp[1][1]=a[1][1];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(i>1)dp[i][j]=max(dp[i][j],dp[i-1][j]+a[i][j]);
if(j>1)dp[i][j]=max(dp[i][j],dp[i][j-1]+a[i][j]);
for(int k=j+j;k<=m;k+=j)
dp[i][k]=max(dp[i][k],dp[i][j]+a[i][k]);
}

printf("%d\n",dp[n][m]);
}
return 0;
}