解题报告 玫瑰花

2.xth的玫瑰花（rose.pas/c/cpp） 描述 这天是rabbit的生日前夕，Xth来到花店，要给他的rabbit买玫瑰花，为了保证质量，他跟花店老板——小菜儿同学要求自己到花田采摘。小菜儿灰常希望早日见到暖熊（xth儿子的小名），于是他决定帮忙。 小菜儿告诉xth，花田是一个n*m的矩形区域，里面有红玫瑰和黑玫瑰两种玫瑰。Xth探明了每一块小区域内红玫瑰和黑玫瑰的种植量，并且还在花田的北边和西边分别设置了红玫瑰和黑玫瑰的收集站（地图上上北下南左西右东）。你的任务是设计一个运输线系统，使得运送的红玫瑰和黑玫瑰的总量最多。 运输线有两种，一种是东西向，一种是南北向。在一个格子内你能建造一种运输线，但不能两种都建。如果两个同类型运输线首尾相接，它们就可以被连接起来。 另外，这些玫瑰都十分不稳定，因此它们在运送过程中都不能拐弯。这就意味着如果某个格子上建有南北向运输线，但是它北边的格子建有东西向运输线。那么这条南北向运输线内运送的任何东西都将丢失。进一步地，运到红玫瑰收集点的黑玫瑰会丢失，运到黑玫瑰收集点的红玫瑰也会丢失。

【输入格式】(rose.in) 第一行包含两个整数n和m，表示花田大小。 以下n行，每行m个整数，其中第i行第j个整数G[ i , j ] 描述各个格子上的黑玫瑰数量。接下来以类似的矩阵表示各个格子上的红玫瑰数量。

【输出格式】(rose.out) 仅一个整数， 表示最多可以采集到的红玫瑰和黑玫瑰的总量。

【输入样例】

4 4

0 0 10 9

1 3 10 0

4 2 1 3

1 1 20 0

10 0 0 0

1 1 1 30

0 0 5 5

5 10 10 10

【输出样例】

98

【数据范围】 对于30%的数据： 0<= n，m <=100; 对于100%的数据： 0<= n, m <=1000; 0<= G[ i, j ] <=1000.

首先，确定这个题的基本思想，动规。 因为它每一个单位方格的权值都不一样，所以贪心不可行。 然后，用一个二维数组记录当转移到这一个点时，如果这一的点向上走最大能得多少分，同样的，如果这一个点向左走最大能得多少分。（最后取 max ） 如果这一个点是向上走的，则这个点之上的点都必须是向上走的，向左走也是同理，由此便可以写出递推式。 这样一来，就又有一个优化，可以预先把每一行，每一列的累和计算出来。

代码 （Leve）

var i,j,n,m:longint;

a,b:array[1..1000,1..1000] of longint;

sum1,sum2:array[0..1000,0..1000] of longint;

f:array[0..1000,0..1000,0..1] of longint;

function max(x,y:longint):longint;

begin

if x>y then exit(x) else exit(y);

end;

begin

assign(input,'rose.in');

assign(output,'rose.out');

reset(input);

rewrite(output);

readln(n,m);

for i:=1 to n do

for j:=1 to m do

read(a[i,j]);

for i:=1 to n do

for j:=1 to m do

read(b[i,j]);

for i:=1 to n do

begin

for j:=1 to m do

sum1[i,j]:=sum1[i,j-1]+a[i,j];

end;

for j:=1 to m do

begin

for i:=1 to n do

sum2[i,j]:=sum2[i-1,j]+b[i,j];

end;

for i:=1 to n do

for j:=1 to m do

begin

f[i,j,0]:=max(f[i,j-1,0],f[i,j-1,1])+sum2[i,j];

f[i,j,1]:=max(f[i-1,j,0],f[i-1,j,1])+sum1[i,j];

end;

writeln(max(f[n,m,1],f[n,m,0]));

close(input);

close(output);

end.

相关知识

解题报告 玫瑰花
有趣的数学解题故事【范文6篇】
玫瑰花市场分析报告
答题与解题（6）
玫瑰花酱工艺描述
玫瑰花市场现状分析及前景预测报告（最新版）
玫瑰花发展趋势分析 中国玫瑰花市场研究与发展趋势报告（2024
洛谷P1854 花店橱窗布置解题报告
玫瑰花观察报告.pptx
环境影响评价报告公示：姚安玫瑰花种植基地建设及系列玫瑰花品精深加工建设地点云环评报告.doc

网址: 解题报告 玫瑰花 https://www.huajiangbk.com/newsview1675587.html