信息学奥赛一本通 1284：摘花生 | OpenJudge NOI 2.6 2728:摘花生

ybt 1284：摘花生
OpenJudge NOI 2.6 2728:摘花生

集合：从左上角起始位置到某位置的路径
限制：到达的位置
属性：采花生数量
条件：最大
统计量：花生数量
状态定义：dp[i][j]：表示从(1,1)走到(i,j)可以采集的最大花生数。

记(i,j)位置的花生数为a[i][j]。
集合：从(1,1)走到(i,j)的路径方案
分割集合：根据最后一步如何走到(i,j)来分割集合。由于每次只能向右或向下走，那么走到(i,j)的前一个位置为：(i-1,j)或(i,j-1)。

• 如果最后一步从(i-1,j)走到(i,j)，从(1,1)走到(i-1,j)能够采集最大花生数为dp[i-1][j]，再加上(i,j)位置的花生数a[i][j]，那么从(1,1)走到(i,j)可以采集的最大花生数为dp[i][j] = dp[i-1][j]+a[i][j]。
• 如果最后一步从(i,j-1)走到(i,j)，从(1,1)走到(i,j-1)能够采集最大花生数为dp[i][j-1]，再加上(i,j)位置的花生数a[i][j]，那么从(1,1)走到(i,j)可以采集的最大花生数为dp[i][j] = dp[i][j-1]+a[i][j]。
• 以上两种情况取最大值

#include 
using namespace std;
#define N 105
int dp[N][N], mp[N][N], t, r, c;//dp[i][j]:从(1,1)走到(i,j)能采到的最大花生数 
int main()
{
    cin >> t;
    while(t--)
    {
        cin >> r >> c;
        for(int i = 1; i <= r; ++i)
            for(int j = 1; j <= c; ++j)
                cin >> mp[i][j];
        for(int i = 1; i <= r; ++i)
            for(int j = 1; j <= c; ++j)
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + mp[i][j];
        cout << dp[r][c] << endl;
    }
    return 0;
}