前言

不知道什么时候写一些算法题，反正只能写一些比较简单的题，哈哈。晚上写一些吧。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int w[N][N];
int f[N][N];
int main(){int t;cin>>t;while(t--){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>w[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){f[i][j]=max(f[i-1][j],f[i][j-1])+w[i][j];}}cout<<f[n][m]<<endl;}return 0;
}

思路

是一个线性 dp 的问题，f 这个数组表示的集合是从左上角的点到 f[i][j] 这个点的路线，属性表示的是最大值，事实上求什么定义的 dp 数组的属性就是什么。然后状态转移就是贪心地求一个最大值并存下来。最后输出答案。