题目描述
第一行是一个整数T,代表一共有多少组数据。
接下来是T组数据。
每组数据的第一行是两个整数,分别代表花生苗的行数R和列数 C。
每组数据的接下来R行数据,从北向南依次描述每行花生苗的情况。每行数据有C个整数,按从西向东的顺序描述了该行每株花生苗上的花生数目M。
对每组输入数据,输出一行,内容为Hello Kitty能摘到得最多的花生颗数。
1≤T≤100 ,
1≤R,C≤100,
0≤M≤1000
样例
2
2 2
1 1
3 4
2 3
2 3 4
165
时间复杂度
n^2
C++ 代码
include [HTML_REMOVED]
//只能向下向左走
//不能从下到上的反向dp,参考898 数字三角形
//可以试试用递归做,递归应该可以反向dp
using namespace std;
const int N = 110;
int row, col, q;
int f[N][N];
int main()
{
cin >> q;
while (q–)
{
cin >> row >> col;
//读入数据
for(int i = 1; i <= row; i++)
for(int j = 1; j <= col; j++)
cin >> f[i][j];
for(int i = 1; i <= row; i++)
for(int j = 1; j <= col; j++)
f[i][j] = max(f[i-1][j], f[i][j-1]) + f[i][j];
cout << f[row][col] << endl;
}
return 0;
}