hdu-2571

版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/40474639

入门的DP 可是我更入门...

根据题目要求， 只能向右或者向下走，向下一次只能走一格。但是如果向右走，则每次可以走一格或者走到该行的列数是当前所在列数倍数的格子，即：如果当前格子是（x,y），下一步可以是（x+1,y），(x,y+1)或者(x,y*k) 其中k>1。

由于幸运值可能为负值，所以初始化dp数组为负数

#include <algorithm>
#include <string.h>
#include <sstream>
#include <stdlib.h>
#include <malloc.h>
#include<bitset>

using namespace std;

int p[25][1010];
int dp[25][1010];

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",&p[i][j]);

        for (int i=0;i<=n;i++)
            for (int j =0;j<=m;j++)
                dp[i][j]=-99999999;

        dp[1][0]=dp[0][1]=0;

        for (int i =1;i<=n;i++)
            for (int j=1;j<=m;j++)
        {
            dp[i][j]=max( dp[i-1][j],dp[i][j-1] );
            for (int k=2;k<=j;k++)
            {
                if (j%k==0)
                dp[i][j]=max(dp[i][j],dp[i][j/k]);
            }
            dp[i][j]+=p[i][j];
        }
        printf("%d\n",dp[n][m]);
    }
    return 0;
}