P1719 最大加权矩形

原题链接

思路：

首先需要回求最大子序列的和，（不会的可以写写这个题最大字段和）
然后这个题就是最大字段和升级版（个人感觉）。
就是把这个二维的矩阵对列利用前缀和进行降维
然后对得到的一维数组进行dp（也就是动态规划求最大值）

方法一：

点击查看代码

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define lop(i,a,b) for(int i = (a); i < (b); i++)
#define dwn(i,a,b) for(int i = (a); i >= (b); i--)
#define mset(t,x) memset(t,x,sizeof(t));
#define ll long long
#define el '\n'using namespace std;int n, ans;
int arr[125][125], brr[125], dp[125];void Arrsum()
{mset(dp, 0);rep(i, 1, n) {dp[i] += max(dp[i - 1] + brr[i], brr[i]);ans = max(dp[i], ans);}
}void solve()
{cin >> n;//读入数据rep(i, 1, n)rep(j, 1, n) cin >> arr[i][j];rep(i, 1, n) {//从第一行开始mset(brr, 0);//对列利用前缀和进行降维rep(j, i, n) {rep(k, 1, n) {brr[k] += arr[j][k];}Arrsum();//dp求最大值}}cout << ans;//输出结果
}int main()
{ios;solve();return 0;
}