【解题报告】洛谷P1719 最大加权矩形

题目链接

https://www.luogu.com.cn/problem/P1719

思路

我们可以看出来，如果这个一维的话，实际上就是一个最大字段和的问题，所以我们还是两个思路，贪心和动态规划，只不过从加一个数字变成了加一列或者加一行

我们可以用二位前缀和来算一行或者一列的东西吧

  1. 贪心

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <string>
    using namespace std;
    int n;
    int ans,a[125][125];
    int main()
    {
    	std::ios::sync_with_stdio(false);
    	cin>>n;
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=n;j++)
    		{
    			cin>>a[i][j];
    			a[i][j]+=a[i-1][j];
    		}
    	}
    	for(int i=1;i<=n;i++)
    	{
    		for(int k=1;k<=i;k++)
    		{
    			int b[150]={0};
    			int f[150]={0};
    			for(int j=1;j<=n;j++)
    			{
    				b[j]=a[i][j]-a[i-k][j];
    				f[j]=max(f[j-1]+b[j],b[j]);
    				ans=max(ans,f[j]);
    			}
    		}
    	}
    	cout<<ans<<'\n';
    	return 0;
    }

  2. 动态规划

    这里介绍一下动态规划的思路

    设 f[i][j]f[i][j] 表示从 (1,1)(1,1) 到 (i,j)(i,j) 这个矩形之内的最大加权矩形，我们就有
    f[i][j]=max(f[i−1][j]+line[i],f[i][j−1]+row[j],f[i−1][j−1]) f[i][j]=max(f[i-1][j]+line[i],f[i][j-1]+row[j],f[i-1][j-1])
    其中 s[i][j]s[i][j] 表示二位前缀和， row,linerow,line 分别可以通过二维前缀和算出来

代码的话？没有代码