http://acm.hdu.edu.cn/showproblem.php?pid=2571
枚举每一个点,找出按照题目要求的这个点的上一点的最大值,合并到当前点,注意只取前面的一种情况
#include<cstdio>
using namespace std;
int val[][];
int max(int x,int y)
{
if (x<y) return y;
else return x;
}
int main()
{
int t,i,j,k,n,m;
while (~scanf("%d",&t)){
while (t--)
{
scanf("%d %d",&n,&m);
for (i=;i<=n;i++)
{
for (j=;j<=m;j++)
{
scanf("%d",&val[i][j]);
val[][j]=-;
}
val[i][]=-;
}
val[][]=val[][]=;
for (i=;i<=n;i++)
{
for (j=;j<=m;j++)
{
int ans=-;
ans=max(ans,val[i-][j]);
ans=max(ans,val[i][j-]);
for (k=;k<j;k++)
{
if (j%k==)
ans=max(ans,val[i][k]);
}
val[i][j]+=ans;
}
}
/*for (i=1;i<=n;i++)
{
for (j=1;j<=m;j++)
printf("%d ",val[i][j]);
printf("\n");
}*/
printf("%d\n",val[n][m]);
}
}
return ;
}