_管道题解_

经验分享区
1

思路：

  1. 不难发现这道题上下的方向与左右如何选取无关，同理左右也与上下无关，也就是说不同行列之间是没有联系的。
  2. 所以就可以直接处理每一行每一列的最大价值和即可。

问题也就简单化了,转换为求出 n+m 个一维数组的最大价值和即可。
那么，如何求就成了一个问题？
观察样例一：

15 -5 100 -40 10 10 10

不难发现：只需要处理相邻三个的最大处理方法，再扩展到全局即可。
那么如何去处理?
其实可以使用 dp 去处理。
核心代码：(以处理行的值为例，列则同理)

  dp[i][j]=max({dp[i][j],dp[i][j-1],dp[i][j-2]+max(0ll,a[i][j-1]+a[i][j])});

部分分得法：

  1. 35pts(n,m<=3)这样做感觉有点偏向正解了，直接暴力枚举每行/列所有情况即可。核心code:（依旧以行为例子）
 if(m==1) ans+=0;
 if(m==2) ans+=max(0ll,a[i][1]+a[i][2]);
 if(m==3) ans+=max({0ll,a[i][1]+a[i][2],a[i][3]+a[i][2]});

貌似dfs暴力也可拿到35pts

  1. 15tps(n=1)
    已经和正解思路大致一致了，只需要处理行的最大价值和即可 ~(也就是比正解少了个dp而已OvO)~核心code与正解相同。
  2. 20tp( n=2 ）
    yd毛丝没有这组数据 和15tps思路大致一样，就是增加了一行的处理，再加上列的值即可(取 max(0) ).
2

%%%tql

3

%%%tql \times 2