hdu 2571 命运（水DP）

题意：

M*N的grid，每个格上有一个整数。

小明从左上角（1，1）打算走到右下角（M，N）。

每次可以向下走一格，或向右走一格，或向右走到当前所在列的倍数的列的位置上。即：若当前位置是（i,j），可以走到（i,k*j）

问取走的最大和是多少。

思路：

水DP。。。边界的初始化要考虑。（因为有负数）。

代码：

int n,m;

int a[30][1005];

int dp[30][1005];

int main(){

    int T;

    cin>>T;

    while(T--){

        cin>>n>>m;

        rep(i,1,n) rep(j,1,m) scanf("%d",&a[i][j]);

        mem(dp,0);

        int ans = 0;

        dp[1][1] = a[1][1];

        rep(i,2,m){

            dp[1][i]=dp[1][i-1]+a[1][i];

            rep(j,1,i-1) if(i%j==0) dp[1][i] = max( dp[1][i],dp[1][j]+a[1][i] );

        }

        rep(i,2,n){

            dp[i][1] = dp[i-1][1]+a[i][1];

            rep(j,1,i-1) if(i%j==0) dp[i][1] = max( dp[i][1],dp[j][1]+a[i][1] );

        }

        rep(i,2,n) rep(j,2,m){

            dp[i][j]=max( dp[i-1][j]+a[i][j],dp[i][j-1]+a[i][j] );

            rep(k,1,j-1) if(j%k==0) dp[i][j]=max( dp[i][j],dp[i][k]+a[i][j] );

        }

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

    }

    return 0;

}

巴特西

hdu 2571 命运（水DP）

最新文章

热门文章