P2706 巧克力

系统管理员 2021-11-26 07:34 201阅读 0赞

## 题目背景 ##

王7的生日到了，他的弟弟准备送他巧克力。

## 题目描述 ##

有一个被分成n\*m格的巧克力盒，在(i,j)的位置上有a\[i,j\]块巧克力。就在送出它的前一天晚上，有老鼠夜袭巧克力盒，某些位置上被洗劫并且穿了洞。所以，你——王7的弟弟王9，必须从这个满目苍夷的盒子中切割出一个矩形巧克力盒，其中不能有被老鼠洗劫过的格子且使这个盒子里的巧克力尽量多。

## 输入输出格式 ##

输入格式：

第一行有两个整数 n、m。第 i+1行的第 j 个数表示a\[ i , j \]。如果这个数为 0 ，则表示这个位置的格子被洗劫过。

输出格式：

输出最大巧克力数。

## 输入输出样例 ##

输入样例\#1：  复制

3 4
    1 2 3 4
    5 0 6 3
    10 3 4 0

输出样例\#1：  复制

17
    //10 3 4这个矩形的巧克力数最大

## 说明 ##

1≤n,m≤300

0≤a\[i,j\]≤255

#include <cmath>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    long long ans,n,m;
    long long s[310],map[310][310],up[310][310];
    int main(){
        scanf("%lld%lld",&n,&m);
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                scanf("%lld",&map[i][j]);
                if(!map[i][j]){
                    map[i][j]=-1<<25;
                }
                up[i][j]=up[i-1][j]+map[i][j];
            }
        }
        for(int i=1;i<=n;++i){
            for(int j=i;j<=n;++j){
                long long mi=0;
                for(int k=1;k<=m;++k){
                    s[k]=s[k-1]+up[j][k]-up[i-1][k];
                }
                for(int k=1;k<=m;++k){
                    ans=max(ans,s[k]-mi);
                    mi=min(s[k],mi);
                }
            }
        }
        printf("%lld",ans);
        return 0;
    }

转载于:https://www.cnblogs.com/xiongchongwen/p/11188249.html