一本通 1284：摘花生

摘花生

思路与最低通行费相似

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
//Mystery_Sky
//
#define M 1010
int a[M][M], f[M][M];
int t, n, m;
int main() {
	scanf("%d", &t);
	while(t--) {
		scanf("%d%d", &n, &m);
		memset(a, 0, sizeof(a));
		memset(f, 0, sizeof(f));
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= m; j++) {
				scanf("%d", &a[i][j]);
				if(i == 1) f[i][j] = f[i][j-1] + a[i][j];
				else if(j == 1) f[i][j] = f[i-1][j] + a[i][j];
			}
		}
		for(int i = 2; i <= n; i++) {
			for(int j = 2; j <= m; j++) {
				f[i][j] = max(f[i-1][j], f[i][j-1]) + a[i][j];
			}
		}
		printf("%d
", f[n][m]);
	}
	return 0;
}