Description

[CCF NOIP2008 T3]

给定一个 N*M 的矩阵A，每个格子中有一个整数。现在需要找到两条从左上角 (1,1) 到右下角 (N,M) 的路径，路径上的每一步只能向右或向下走。路径经过的格子中的数会被取走。两条路径不能经过同一个格子。求取得的数之和最大是多少。N,M≤50。

数据规模约定：

30%的数据满足：1<=m,n<=10

100%的数据满足：1<=m,n<=50

Input Format

第一行有2个用空格隔开的整数n和m，表示有n行m列（1<=n,m<=50）。 接下来的n行是一个n*m的矩阵，每行的n个整数之间用空格隔开。

Output Format

一个整数，表示答案。

3 3
0 3 9
2 8 5
5 7 0​

34​

Source

动态规划