• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

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

开发技术 开发技术 2周前 (10-11) 8次浏览

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

题目链接

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

思路

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

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

  1. 贪心

    #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]) 表示从 ((1,1))((i,j)) 这个矩形之内的最大加权矩形,我们就有

    [f[i][j]=max(f[i-1][j]+line[i],f[i][j-1]+row[j],f[i-1][j-1])
    ]

    其中 (s[i][j]) 表示二位前缀和, (row,line) 分别可以通过二维前缀和算出来

代码的话?没有代码


程序员灯塔
转载请注明原文链接:【解题报告】洛谷P1719 最大加权矩形
喜欢 (0)