吐槽
滚动

2017 C语言积分赛 周赛一 E题 纯洁的交情交易 题解

题目描述

菲奥德尔·杰斯曼和玛尔歌·梅迪西斯是好朋友也是好邻居,他们在一起总有谈不完的话题。但是在艾尔佩斯事变后,一切都变了。

现在,菲奥德尔在第一行第一列的一号浮游岛,而玛尔歌在第n行第m列的末位浮游岛。每次送信只能往下一行同一列或是下一列同一行的浮游岛送信。

菲奥德尔希望通过自己在护翼军的四等武官身份假托公事向玛尔歌送一封信,并期待能够得到她的回信。但是只能让每个浮游岛的护翼军帮一次忙而已,否则会让人怀疑自己滥用职权。

而每个浮游岛的护翼军都与菲奥德尔有一定的交情。为了事后能更容易还上人情,菲奥德尔希望在信件来回的路上所经过的护翼军的交情总和最大。请你帮他算算吧。

输入

第一行有2个用空格隔开的整数n和m,表示浮游大陆有n行m列的浮游岛。

接下来的n行是一个n*m的矩阵,矩阵中第i行j列的整数表示在第i行j列浮游岛的护翼军与菲奥德尔的交情。每行的m个整数之间用空格隔开。

100%的数据满足:1<=m,n<=50
所有数据小于maxint

输出

共一行,包含一个整数,表示来回两条路上参与传递信件的护翼军与菲奥德尔交情之和的最大值。

样例输入

样例输出

双线程DP。可以视为两个人从起点开始同时前进。

思路:

1、确定状态转移方程。

状态转移方程:

f[x1][y1][x2][y2]=maxn(f[x1-1][y1][x2-1][y2],f[x1-1][y1][x2][y2-1],f[x1][y1-1][x2-1][y2],f[x1][y1-1][x2][y2-1])+d[x1][y1];

其中d[x1][y1]表示在(x1,y1)位置上的护翼军与菲奥德尔的交情。

2、为了保证两个人不经过同一个点,需附加判断。

if(x1!=x2&&y1!=y2) f[x1][y1][x2][y2]+=d[x2][y2];

3、输出时结果只能为f[n][m-1][n-1][m]或f[n-1][m][n][m-1],而不能是f[n][m][n][m]。(因为两人不能经过同一个点)

Code:

 

dp
Contents licensed under Creative Commons by-nc-sa 3.0.
Post Comment

Post Comment