首页 > 其他分享 >最大加权矩形

最大加权矩形

时间:2023-04-11 20:58:26浏览次数:50  
标签:加权 最大 nn int 矩阵 130 127 矩形

题目描述

为了更好的备战 NOIP2013,电脑组的几个女孩子 LYQ,ZSC,ZHQ 认为,我们不光需要机房,我们还需要运动,于是就决定找校长申请一块电脑组的课余运动场地,听说她们都是电脑组的高手,校长没有马上答应他们,而是先给她们出了一道数学题,并且告诉她们:你们能获得的运动场地的面积就是你们能找到的这个最大的数字。

校长先给他们一个 n\times nn×n 矩阵。要求矩阵中最大加权矩形,即矩阵的每一个元素都有一权值,权值定义在整数集上。从中找一矩形,矩形大小无限制,是其中包含的所有元素的和最大 。矩阵的每个元素属于 [-127,127][−127,127] ,例如

 0 –2 –7  0 
 9  2 –6  2
-4  1 –4  1 
-1  8  0 –2

在左下角:

9  2
-4  1
-1  8

和为 1515。

几个女孩子有点犯难了,于是就找到了电脑组精打细算的 HZH,TZY 小朋友帮忙计算,但是遗憾的是他们的答案都不一样,涉及土地的事情我们可不能含糊,你能帮忙计算出校长所给的矩形中加权和最大的矩形吗?

输入格式

第一行:nn,接下来是 nn 行 nn 列的矩阵。

输出格式

最大矩形(子矩阵)的和。

输入输出样例

输入 #1
4
0 -2 -7 0
 9 2 -6 2
-4 1 -4  1 
-1 8  0 -2
输出 #1
15
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
int a[130][130],dp[130],presum[130][130];
//presum记录行前缀和
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> a[i][j];
            presum[i][j] = presum[i - 1][j] + a[i][j];
        }
    }
    int maxn = a[1][1];
    for (int x1 = 1; x1 <= n; x1++)
    {
        for (int x2 = x1; x2 <= n; x2++)
        {
            for (int j = 1; j <= n; j++)
            {
                dp[j] = presum[x2][j] - presum[x1-1][j];
            }
            for (int i = 1; i <= n; i++)
            {
                dp[i] = max(dp[i], dp[i - 1] + dp[i]);maxn = max(maxn, dp[i]);
            }
            
        }
    }
    cout << maxn;
    return 0;
}

 

标签:加权,最大,nn,int,矩阵,130,127,矩形
From: https://www.cnblogs.com/wakeendblogs/p/17307661.html

相关文章

  • 2023-04-10 网络流和最大流问题
    网络流和最大流问题1网络流和最大流问题阐述网络流基本概念网络流图中,从源点出发,在满足每条边容量限制的条件下,汇点t最多能接收多少流量s:sourcet:target网络流需要满足的限制容量限制平衡限制:除了源点s和汇点t,对于每一个点,流入量等于流出量从源点s流出的流量,一定......
  • 搜索系统和推荐系统最大不同
     在脉脉上看到一个回答:1.搜索多了query,要保证内容相关性,容错率低;推荐容错率高,还需要一定的多样性和发现性。2.基于1,决定了搜索在召回阶段,兼顾相关行性和个性化,而推荐只需要个性化;在排序阶段,搜索目标是强偏序关系,识别物料的细微差别,通常用pairwise或listwise,推荐关心用户是否......
  • GridSplitter使用,包括最大最小限制
     <Windowx:Class="WpfApp1.PageWindow"xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"xmlns:ribbon="clr-namespace:Mic......
  • Stata中的治疗效果:RA:回归调整、 IPW:逆概率加权、 IPWRA、 AIPW|附代码数据
    全文链接:http://tecdat.cn/?p=10148最近我们被客户要求撰写关于Stata中的治疗效果的研究报告,包括一些图形和统计输出。今天的主题是Stata中的治疗效果。治疗效果估算器根据观察数据估算治疗对结果的因果关系。我们将讨论四种治疗效果估计量:RA:回归调整IPW:逆概率加权I......
  • 1363. 形成三的最大倍数
    题目描述给一个整数数组问怎么选数字,可以让能得到的结果最大,同时这个接结果需要是3的倍数?f1分类讨论+贪心基本分析怎么判断能不能被3整除?和%3==0怎么判断该从数组中删掉哪些数字?(1)和%3==1,删最小的余1的数字,不行删俩最小的余2的数字;(2)和%3==2,删最小的余2的数字或者......
  • MFC-FrameRect绘制矩形边框
     HDChdc=::GetDC(m_hWnd);RECTrect={10,10,50,100};HBRUSHhbr;hbr=CreateSolidBrush(RGB(255,0,0));intf=FrameRect(hdc,&rect,hbr);//绘制矩形边框/*参数1:HDChdc将要画边框的设备环境句柄参数2:CONSTRECT......
  • MFC-FillRect绘制并填充矩形
     HDChdc=::GetDC(m_hWnd);RECTrect={10,10,50,100};HBRUSHhbr;hbr=CreateSolidBrush(RGB(255,0,0));SelectObject(hdc,hbr);intf=FillRect(hdc,&rect,hbr);//绘制并填充矩形/*用指定的画刷填充矩形,此函数包......
  • MFC-Rectangle绘制矩形
     HDChdc=::GetDC(m_hWnd);::MoveToEx(hdc,0,0,NULL);HPENhpen=CreatePen(PS_SOLID,3,RGB(0,0,255));SelectObject(hdc,hpen);BOOLb=Rectangle(hdc,0,0,50,100);//绘制矩形/*该矩形用当前画笔绘制轮廓,用当前画刷填充......
  • 【解决】Windows10如何限制CPU最大使用率?
    【问题】Windows10如何限制CPU最大使用率?【解决】:进入控制面板→电源选项→更改计划设置→更改高级电源设置→处理器电源管理,最大处理器状态。设置需要的百分比即可。  ......
  • 用 Go 剑指 Offer 42. 连续子数组的最大和
    输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。 示例1:输入:nums=[-2,1,-3,4,-1,2,1,-5,4]输出:6解释: 连续子数组 [4,-1,2,1]的和最大,为 6。 提示:1<= arr.length<=10^5-100<=arr[i]<=100......