POJ1050 To the Max

冷不防 2022-01-13 10:07 182阅读 0赞

题目链接：[contest-hunter.org:83/contest/0x08「基本算法」练习/POJ1050][contest-hunter.org_83_contest_0x08_POJ1050] To the Max

我就是个菜鸡。 啥都不会 呜呜呜

这个题目可以说是一个dp了。也可以说是思维吧。有点难想。

我们可以用三层循环。第一层循环是枚举区间的左列。第二层循环是枚举区间的右列。  
第三层循环则是枚举每一行。 这样的话就可以通过三层循环来表示出一个区间，不需要通过四层循环了。看图所示 。 黄色部分为k的一次遍历 红色部分为k的另一次遍历。  
通过，这样不断枚举，势必所有的区间都会被遍历到。然后在k的一次遍历中，需要做的就是不断的求出最优解，用一个变量sum不断累加黄色部分。当黄色部分为负数的时候，就重置sum。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTA2MTM4_size_16_color_FFFFFF_t_70]

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    
    int N;
    int num[1000][1000];
    int sum[1000][1000];
    int dp[110][110][110];
    
    int main()
    {
        scanf("%d",&N);
        int mark = 0;
        int m = -1000010;
        for(int i = 1; i <= N;i ++)
            for(int j = 1; j <= N; j ++)
            {
                scanf("%d",&num[i][j]);
                if(num[i][j] > 0) mark = 1;
                m = max(m,num[i][j]);
                sum[i][j] = sum[i][j - 1] + num[i][j];
            }
        if(mark == 0)
        {
            printf("%d\n",m); return 0;
        }
        int maxx = -100010;
        int now_max = 0;
        for(int i = 0; i <= N;i ++)
        {
            for(int j = i; j <= N;j ++)
            {
                now_max = 0;
                for(int k = 1; k <= N;k ++)
                {
                    now_max += sum[k][j] - sum[k][i];
                    if(now_max < 0)
                        now_max = 0;
                    maxx = max(maxx,now_max);
                }
            }
        }
        printf("%d\n",maxx);
        return 0;
    }

[contest-hunter.org_83_contest_0x08_POJ1050]: http://contest-hunter.org:83/contest/0x08%E3%80%8C%E5%9F%BA%E6%9C%AC%E7%AE%97%E6%B3%95%E3%80%8D%E7%BB%83%E4%B9%A0/POJ1050
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTA2MTM4_size_16_color_FFFFFF_t_70]: /images/20220113/b750a4401b104e04808c6ef9607f72f0.png