【2016.10.5NOIP普及模拟】zy送画

发布于 2019-04-10  927 次阅读


题目描述

话说在军训的倒数第二天,zy终于下定决心要将画了10天之久的画像送给他心怡的法学院mm。但是,他不敢自己一个人去,倒霉的kk只能和他一起去了。不过,为了表现的有诚意,kk和zy不能走在一起,要不然被对方看见就不好了。那么到底要怎么走呢?zy给了kk一幅地图,他把学校分成了n*m个格子,对于每个格子,zy写下了一个数字表示他对于这个格子的好感度(好感度当然是zy自己定义的),入口在左上角(1,1)点,出口在右下角(n,m),zy和kk需要从左上角一起出发,在右下角会和,因为zy非常害羞,所以中间kk和zy都只向右或向下走,这样走完全程的时间最短,但中间两人不能走到同一个格子上。经过深思熟虑,他决定,需要他和kk走的路的好感度总和最大才是最好。现在,zy和kk希望你能告诉他们两个人各自要走那一条路。为了简化问题,你只需告诉他们两个好感度总和就可以了。你可以假设mm一定会在zy的路上。

输入

第一行两个整数n,m。
接下来n行每行m个整数,每两个整数之间用一个空格隔开。

输出

一行一个整数表示最大好感度和。注意,起点和终点的好感度值只计入一次。

思路

一个四维dp,和普通的最短路径问题相似,就是要多枚举一条路而已

onst
  maxn=51;
type 
  arraytype=array [0..maxn,0..maxn] of longint;
var 
  i,j,k,n,i1,i2,j1,j2,m:longint;
  data:arraytype;
  sum:array [0..maxn,0..maxn,0..maxn,0..maxn] of longint;
function max(x,y:longint):longint;
begin
  if x>y then max:=x else max:=y;
end;
begin 
  assign(input,'paint.in'); reset(input);
  assign(output,'paint.out'); rewrite(output);
  for i:=1 to maxn do
    for j:=1 to maxn do 
      data[i,j]:=0;
  readln(n,m);
  for i:=1 to n do
    begin
      for j:=1 to m do 
        read(data[i,j]);
      readln; 
    end;
  fillchar(sum,sizeof(sum),0);
  for i1:=1 to n do
    for j1:=1 to m do
      for i2:=1 to n do
        for j2:=1 to m do
          begin
            if sum[i1-1,j1,i2-1,j2]>sum[i1,j1,i2,j2]
              then sum[i1,j1,i2,j2]:=sum[i1-1,j1,i2-1,j2];
            if sum[i1-1,j1,i2,j2-1]>sum[i1,j1,i2,j2]
              then sum[i1,j1,i2,j2]:=sum[i1-1,j1,i2,j2-1];
            if sum[i1,j1-1,i2-1,j2]>sum[i1,j1,i2,j2]
              then sum[i1,j1,i2,j2]:=sum[i1,j1-1,i2-1,j2];
            if sum[i1,j1-1,i2,j2-1]>sum[i1,j1,i2,j2]
              then sum[i1,j1,i2,j2]:=sum[i1,j1-1,i2,j2-1];
            sum[i1,j1,i2,j2]:=sum[i1,j1,i2,j2]+data[i1,j1];
            if (i1<>i2) or (j1<>j2)
              then sum[i1,j1,i2,j2]:=sum[i1,j1,i2,j2]+data[i2,j2]
          end;
  writeln(sum[n,m,n,m]);
end.
]]>