C语言题（方格取数）

Question

方格取数(grid.cpp)
问题描述：
给一个n行m列的网格，每个格子里都有一个整数(正负任意)，每一步只能向下或向右：向下一次只能走一格；但是如果向右走，则每次可以走一格或者走到该行的列数是当前所在列数倍数的格子，即：如果当前格子是（x,y），下一步可以是（x+1,y），(x,y+1)或者(x,y*k) 其中k>1。编程计算从左上角(1,1)走到右下角(n,m)所经过的格子的数字和的最大值。
输入格式：
第一行为两个整数n和m(1≤n≤20,10≤m≤1000)，表示网格大小；接下来n行，每行m个整数，表示对应格子里的整数ti(|ti|<100)。
输出格式：
仅一个整数，表示最大和值。

Answer 1

/*
方格取数(grid.cpp)

问题描述：

给一个n行m列的网格，每个格子里都有一个整数(正负任意)，每一步只能向下或向右：
向下一次只能走一格；但是如果向右走，则每次可以走一格或者走到该行的列数是当前所在列数倍数的格子，
即：如果当前格子是（x,y），下一步可以是（x+1,y），(x,y+1)或者(x,y*k) 其中k>1。
编程计算从左上角(1,1)走到右下角(n,m)所经过的格子的数字和的最大值。

输入格式：

第一行为两个整数n和m(1≤n≤20,10≤m≤1000)，表示网格大小；
接下来n行，每行m个整数，表示对应格子里的整数ti(|ti|<100)。

输出格式：

仅一个整数，表示最大和值。
Author:Im_hear
*/
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;

int N,M;
int map[21][1001]={0};
int ans[21][1001]={0};
int factor[1001][33]={0};
int fun(int row);
int init(int row);

int main()
{
int x,y;
scanf("%d%d",&N,&M);
init(N);
for(x=1;x<=N;++x){
for(y=1;y<=M;++y){
scanf("%d",&map[x][y]);
}
}
for(x=1;x<=N;++x){
//理解为输入的矩阵只有一行
fun(x);
}
printf("%d\n",ans[N][M]);
return 0;
}

/*将第row行每个位置能达到的最大值记录到ans[row][]行中*/
int fun(int row)
{
int i,index,y,step=1,maxPre,iCount;
int temp = 0;
//第一列只能从上行过来
ans[row][1] = ans[row-1][1] + map[row][1];
for(y=2;y<=M;++y){
//假设从左边过来时,累加的值最大
maxPre = ans[row][y-1];
if(row>1 && ans[row-1][y]>maxPre){
//假设从上边过来时,累加的值最大
maxPre = ans[row-1][y];
}
//取得y的因数个数
iCount = factor[row][0];
for(i=1;i<=iCount;++i){
//取得y的第i个因数
index = factor[row][i];
//比原先更好的路线,从(row,factor[row][i])位置过来
if(ans[row][index] > maxPre){
maxPre = ans[row][index];
}
}
//更新当前位置的最大累计值
ans[row][y] = maxPre + map[row][y];
}
/*
//去掉注释可以看到每行的变化
for(y=1;y<=M;++y){
printf("%3d, ",ans[row][y]);
}
printf("\n");
*/
return 0;
}

/*储存1000内每个数的因数*/
int init(int row)
{
int x,y,icount,step;
factor[1][1] = 1;
for(x=2;x<=row;++x){
icount=1;
//x是奇数时，因数都是奇数，步长可设为2
step = x&1?2:1;
y = x&1?1:2;
for(;y<=x/2;y+=step){
if(x%y == 0){
factor[x][icount++] = y;
}
}
factor[x][0] = icount-1;
}
return 0;
}

Answer 2

可以用递归的方式计算。