题目描述

blablabla

样例

blablabla

算法1

正常线性dp

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;

const int N=110;
int a[N][N],f[N][N];

int main()
{
int n;
cin>>n;
while(n–)
{

    memset(f,0,sizeof f);
    int r,c;
    cin>>r>>c;
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++) cin>>a[i][j];


    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            f[i][j]=max(f[i-1][j]+a[i][j],f[i][j-1]+a[i][j]);
        }
    }


    cout<<f[r][c]<<endl;
}

return 0;

}

blablabla

算法2

记忆化搜索

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;

const int N=110;
int a[N][N],f[N][N];
int r,c;
int x[2]={-1,0},y[2]={0,-1};
int dp(int i,int j)
{
if(f[i][j]!=-1) return f[i][j];
for(int k=0;k<2;k++)
{
int dx=i+x[k],dy=j+y[k];
if(dx>0&&dx<=r&&dy>0&&dy<=c)
f[i][j]=max(f[i][j],dp(dx,dy)+a[i][j]);
}

return f[i][j];

}

int main()
{
int n;
cin>>n;
while(n–)
{

    memset(f,-1,sizeof f);


    cin>>r>>c;
    for(int i=0;i<=r;i++) f[i][0]=f[0][i]=0;
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++) cin>>a[i][j];

    f[1][1]=a[1][1];
    int m=dp(r,c);

   cout<<m<<endl;
}

return 0;

}