http://acm.hdu.edu.cn/showproblem.php?pid=2571
类似于数塔,因为约数那里WA了N次,仔细啊仔细。。。
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int INF = 0x3f3f3f3f; int map[25][1010]; int dp[25][1010]; int main() { int n,m; int test; scanf("%d",&test); while(test--) { memset(dp,-INF,sizeof(dp)); memset(map,-INF,sizeof(map)); scanf("%d %d",&n,&m); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) scanf("%d",&map[i][j]); dp[1][1] = map[1][1]; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if(i == 1 && j == 1) continue; int tmp = max(dp[i-1][j],dp[i][j-1]); for(int k = 2; k <= j; k++) { if(j%k == 0) tmp = max(tmp,dp[i][j/k]); } dp[i][j] = map[i][j] + tmp; //printf("%d %d :%d\n",i,j,dp[i][j]); } } printf("%d\n",dp[n][m]); } return 0; }