AcWing 1015. 摘花生
原题链接
简单
作者:
kingss
,
2022-02-28 16:11:25
,
所有人可见
,
阅读 170
好久没写了,都手生了。插件先暂停更新,让我好好研究。
#include <iostream>
#include <algorithm>
#define Min 0xcfcfcfcf
using namespace std;
const int N = 1e+4+10 ;
int T ,R , C ,g[N][N] , f[N][N];
int cup(){
for(int i = 1 ; i <= R ; i ++) {
f[i][1] = g[i][1] + f[i-1][1] ;
}
for(int i = 1 ; i <= C ; i ++ ){
f[1][i] = g[1][i] + f[1][i-1] ;
}
for(int i = 2 ; i <= R ; i ++ )
for(int j = 2 ; j <= C ; j ++ ){
f[i][j] = max(f[i-1][j],f[i][j-1])+g[i][j] ;
}
return f[R][C] ;
}
int main()
{
ios::sync_with_stdio(false) ;
cin >> T ;
while(T --){
cin >> R >> C ;
for(int i = 1 ; i <= R ; i ++){
for(int j = 1 ; j <= C ; j ++ ) {
cin >> g[i][j] ;
}
}
cout << cup() << endl ;
}
return 0 ;
}