首页 > 代码库 > hdu 2571 G++

hdu 2571 G++

# include <stdio.h>int a[25][1010], vis[25][1010] ;int n, m, INF = 0x0f0f0f0f ;int max(int a, int b){return a>b?a:b;}int dfs(int x, int y){    int i, rtn = -INF ;    if (x == n && y == m) return a[x][y] ;    if (vis[x][y] != INF) return vis[x][y] ;//  访问        if (x < n) rtn = max(rtn, dfs(x+1, y)) ;    if (y < m) rtn = max(rtn, dfs(x, y+1)) ;        for (i = y * 2 ; i <= m ; i+=y)        rtn = max(rtn, dfs(x, i)) ;    return vis[x][y] = rtn + a[x][y] ;  //原有的  +  该点的 }int main (){    int T, i, j ;    scanf ("%d", &T) ;    while (T--)    {        scanf ("%d%d", &n, &m) ;        for (i = 1 ; i <=n ; i++)            for (j = 1 ; j <= m ; j++)            {                vis[i][j] = INF ;             // 没有访问过 ,,标记                 scanf ("%d", &a[i][j]) ;            }        printf ("%d\n", dfs(1,1)) ;    }    return 0 ;}
View Code

 

 

# include <stdio.h>

int a[25][1010], vis[25][1010] ;
int n, m, INF = 0x0f0f0f0f ;

int max(int a, int b){return a>b?a:b;}

int dfs(int x, int y)
{
    int i, rtn = -INF ;
    if (x == n && y == m) return a[x][y] ;
    if (vis[x][y] != INF) return vis[x][y] ;//  访问
   
    if (x < n) rtn = max(rtn, dfs(x+1, y)) ;
    if (y < m) rtn = max(rtn, dfs(x, y+1)) ;
   
    for (i = y * 2 ; i <= m ; i+=y)
        rtn = max(rtn, dfs(x, i)) ;

    return vis[x][y] = rtn + a[x][y] ;  //原有的  +  该点的
}


int main ()
{
    int T, i, j ;
    scanf ("%d", &T) ;
    while (T--)
    {
        scanf ("%d%d", &n, &m) ;
        for (i = 1 ; i <=n ; i++)
            for (j = 1 ; j <= m ; j++)
            {
                vis[i][j] = INF ;             // 没有访问过 ,,标记
                scanf ("%d", &a[i][j]) ;
            }
        printf ("%d\n", dfs(1,1)) ;
    }
    return 0 ;
}