首页 > 代码库 > Omar Loves Candies

Omar Loves Candies

2024-07-13 04:14:22   213人阅读

题目大意：在一个N * M的格子中，放有一些糖，这些糖有的会损害健康，有的对健康有益。有损害的被记为负数，有益的会记为正数。另外，对于每一个糖而言，他都比左边的糖和上面的糖更健康。

现在我要在在N*M这个矩阵中找到一个子矩阵，使得所有糖的有益值加起来最大。

题目已经是简化了的。糖果按照左上最小，右下最大的顺序排列好了。所以很明显从右下角的糖是肯定要拿走的，所以从这个格子开始枚举。但是枚举的话会超时，该怎么处理呢？

再想一下，发现题目不涉及更新操作，只有求和的部分。所以可以预处理出所有的和，并存在对应的格子中。比如map[i][j]中存着 map[ 1..i ][ 1..j ]共计 i * j 个数的和。这样只要遍历所有格子，取出最大值就可以了。这样算法的复杂度就变成 O(nm)了。很明显可以接受，而且写法也简单。

特别的，这里可以有一些特殊处理，可以更方便的写代码。

例如输入的时候从(m, n)开始输入，让最大值的位置变到左上角，最小值到右下角。

求和的时候一个一个累加过去 map[ i ][ j ] += map[ i ][ j-1 ]，之后再 map[ i ][ j ] += map[ i–1 ][ j ]。这样就能保证map[ i ][ j ]存的是其左上角的所有格子的和。

下面附上代码：

/* * Problem: I *    Date: 2014-7-20 *  Author: Wuhen*/#include <map>#include <list>#include <queue>#include <string>#include <vector>#include <cstdarg>#include <stdio.h>#include <string.h>#include <stdlib.h>#include <iostream>#include <algorithm>#define LL __int64#define Clean(a) memset(a, 0, sizeof(a))using namespace std;LL ditu[1009][1009];LL max(LL a, LL b){    return ((a > b) ? a : b);}int main(){    std::ios::sync_with_stdio(false);    LL n, m;    LL T;    scanf("%I64d", &T);    while(T--)    {        scanf("%I64d%I64d", &n, &m);        Clean(ditu);        for (LL i = n; i > 0; i--)            for (LL j = m; j > 0; j--)                scanf("%I64d", &ditu[i][j]);                        for (LL i = 1; i <= n; i++)            for (LL j = 2; j <= m; j++)                ditu[i][j] += ditu[i][j-1];                for (LL i = 2; i <= n; i++)            for (LL j = 1; j <= m; j++)                ditu[i][j] += ditu[i-1][j];                        LL res = ditu[1][1];                for (LL i = 1; i <= n; i++)            for (LL j = 1; j <= m; j++)                res = max(res, ditu[i][j]);        printf("%I64d\n", res);    }    return 0;}


联系
我们