游客 注册 | 登录
中文 | En

2765 - 矩阵

通过次数

0

提交次数

0

时间限制 : 11 秒 内存限制 : 130 MB

一个 N M的坐标平面（（0，0）〜（N，M））。最初所有N M个网格的值是0。 
一个运算T（A，B，H，X，Y）被定义如下： 
1，在矩阵（X，Y）〜（X +α，γ+ b）中找出最大的值，假设的最大值为 max

2，在矩阵（X，Y）〜（X + A，Y+ B）更改所有的值为 max + H 


在C次这样的操作后，请输出在整个N * M个网格中的最大值。 

题目输入

输入包括几个案例。 

对于每一种情况下，第一行包含三个正整数N，M及C（N≤1000，M≤1000，C≤1000）。下面的C行，每行包括5个非负数, ai, bi, hi, xi, yi (0 ≤ hi ≤ 10000, 0 ≤ xi < n, 0 ≤ yi < m).

题目输出

对于每一种情况下，输出最大值

输入/输出样例

输入格式

3 2 2
2 1 9 1 1
1 1 2 2 1

输出格式

11

C++解答

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <iostream>
using namespace std;
int Map[1001][1001];
int main ()
{
	int n, m, i, j, k, len, c;
	int a, b, h, x, y, max, max2, ii, jj, jjj;
	
	while(scanf("%d%d%d",&n,&m,&c) != EOF)
	{
		memset(Map,0,sizeof(Map));
		max2 = -1;
		for(k = 0 ; k < c ; k ++)
		{
			scanf("%d%d%d%d%d",&a,&b,&h,&x,&y);
			max = -1;
			for(i = x + 1; i <= x + a ; i ++)
			{
				for(j = y + 1; j <= y + b ; j ++)
				{
					if(Map[i][j] > max)
					{
						max = Map[i][j];
						ii = i;
						jj = j;
					}
					else
						Map[i][j] = max + h;
				}
			}

			for(i = x + 1 ; i <= ii ; i ++)
			{
				if(i == ii)
					jjj = jj;
				else
					jjj = y + b;
				for(j = y + 1 ; j <= jjj ; j ++)
				{
					Map[i][j] = max + h;
				}
			}
			if(max + h > max2)
					max2 = max + h;
		}

		printf("%d\n",max2);
	}
	return 0;
}
请先登陆