题目描述

blablabla

样例

blablabla

算法1

(动态规划) $O(nm)$

#include <iostream>
#include <cstring>
using namespace std;
const int N=110;
const int M=110;
int hua[N][M];
int dp[N][M];
int main(){
    int c;
    cin>>c;
    while(c--){
        int n,m;
        cin>>n>>m;
        memset(hua,0,sizeof(hua));
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>hua[i][j];

        for(int i=1;i<m;i++)
            dp[1][i]=hua[1][i];
        for(int i=1;i<n;i++)
            dp[i][1]=hua[i][1];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                if(i>1)
                    dp[i][j]=max(dp[i][j],hua[i][j]+dp[i-1][j]);
                if(j>1)
                    dp[i][j]=max(dp[i][j-1]+hua[i][j],dp[i][j]);

            }
        cout<<dp[n][m]<<endl;


    }
}

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla