之江学院第0届 B qwb与矩阵简单dp 或记忆化搜索-白红宇

之江学院第0届 B qwb与矩阵简单dp 或记忆化搜索

阅读量：6385 次

发布时间：2019-06-23

本文共 2070 字，大约阅读时间需要 6 分钟。

　　题目链接： http://115.231.222.240:8081/JudgeOnline/problem.php?cid=1005&pid=1

　　题目大意：给出一个矩阵，求出从左上角到右下角的最大加权和，其中有三种转移方式，向下走一个，向右走一个，向右走自己当前坐标的整数倍个

　　解题思路：硬搞就可以了，记忆化搜索行， dp也可以

　　代码：

int a[25][10007];int dp[25][10007];const int INF = 0x3fffffff;int main() {    int t;    scanf( "%d", &t );    while( t-- ) {        int n, m;        scanf( "%d%d", &n, &m );        for( int i = 1; i <= n; i++ ) {            for( int j = 1; j <= m; j++ ) {                scanf( "%d", &a[i][j] );                dp[i][j] = -INF;            }        }        dp[1][1] = 0;        for( int i = 1; i <= n; i++ ) {            for( int j = 1; j <= m; j++ ) {                dp[i][j] += a[i][j];                if( i < n ) dp[i+1][j] = max( dp[i+1][j], dp[i][j] );                if( j < m ) dp[i][j+1] = max( dp[i][j+1], dp[i][j] );                for( int k = 2; k * j <= m; k++ ) {                    dp[i][k*j] = max( dp[i][k*j], dp[i][j] );                }            }        }        printf( "%d\n", dp[n][m] );    }    return 0;}

#include 
      
       #include 
       
        using namespace std;int a[25][10007];int dp[25][10007];int dir[2][2] = {
    {
    0, 1}, {
    1, 0}};const int INF = 0x3fffffff;int n, m;int dfs( int x, int y ) {    if( dp[x][y] > -INF ) return dp[x][y];    int temp = -INF;    for( int i = 0; i < 2; i++ ) {        int tx = x + dir[i][0];        int ty = y + dir[i][1];        if( tx <= n && ty <= m ) temp = max(temp, dfs(tx, ty));    }    for( int i = 2; i * y <= m; i++ ) {        temp = max( temp, dfs(x, i*y) );    }    dp[x][y] = max( dp[x][y], a[x][y] + temp );    return dp[x][y];}int main() {    int t;    scanf( "%d", &t );    while( t-- ) {        scanf( "%d%d", &n, &m );        for( int i = 1; i <= n; i++ ) {            for( int j = 1; j <= m; j++ ) {                scanf( "%d", &a[i][j] );                dp[i][j] = -INF;            }        }        dp[n][m] = a[n][m];        cout << dfs(1, 1) << endl;    }    return 0;}