链接 这个链接是easy版本
链接 这个链接是hard版本
前言：看hard版本题解最好把easy版本的给看了，本文较长，在博客内看体验更好
这个题给我留下的印象很深刻，应该说这场比赛都给我留下了深刻的印象，比赛开局看半天才看懂A啥意思，磕磕碰碰16分钟的时候AC了，之后的一个半小时一直在盯着BC看，说实话，贪了，我一开始想着一口气给hard写出来，但是看半天实在没啥想法，就去看easy版本，盯了一个多小时，勉强看出来了，然后最后写完加调试搞好之后，比赛已经结束五分钟了，快给我气爆了，主要是调试花了十来分钟的时间，问题出在我没把dp数组初始化成负无穷。现在就先说一下easy版本。
这个easy版本，我看这个题意的意思，感觉有点像数字三角形模型，就是那种：
你一开始在二维矩阵上的某个点，二维矩阵的每个点都有一个权值，然后你只能往下走或者往右走，问你最后抵达右下角的时候，路径权值之和最大是多少。
这个问题的dp转移方程很好理解，就是 dp[i][j]=max(dp[i-1][o],dp[i][o-1])+a[i][o] ;
但是这个题有个特别不一样的地方，那就是它走到某一列最下方再往下面走，会回到当前列的最上方，而且它每个点只能经过一次，我就想哎呀，这咋搞，这样的话就不能按照刚刚那个dp的转移方程来写了，因为这样就破坏了dp的无后效性，对dp的无后效性我是这样理解的，就是我们的dp转移过程中会有一个顺序，就比如刚刚的数字三角形模型，它的转移顺序就是:
for(int i=1;i<=n;i++)
{
for(int o=1;o<=m;o++)
{
dp[i][j]=max(dp[i-1][o],dp[i][o-1])+a[i][o];
}
}
在这个转移顺序之下，我们dp的转移方程是成立的，因为之后的状态显然不会影响到我们当前的状态。
所以说要是那个方程放到这个题里面，肯定就完犊子了，因为假如说我们要这样转移，那它从下面传送回上面的情况会影响到我们之前已经转移好的状态 ,啊，然后我就卡了一会儿，然后我突然又发现我可以重新构造一个矩阵，然后让它们挨个拼在一起，就那第一个样例来解释吧，拼起来之后就像下面这样
这是原来的样子
1 2 3
4 5 6
7 8 9
这是拼起来的样子
1 2 3
4 5 6
7 8 9
1 2 3
4 5 6
7 8 9
1 2 3
4 5 6
7 8 9
这样有多少列我就复制多少份，然后再拼起来，这是因为它每次到某一列的最后一行都可以回到最上面，那我直接把矩阵变成这样再去用数字三角形模型的转移方程转移是否可行呢?
很快我就发现不可行hhh，因为它有个限制，那就是每个点都只能走一次，如果是拼起来的话，那可能一个点因为它的值比较大，被走了好几次，如果我们想记录这个点是否被走过，那特别的麻烦，而且时间复杂度也会supper爆炸，因为它的情况数很多，每种情况都记录，那直接就寄了，不用想的都，然后我就陷入了一个思维闭环，就像是被那个数字三角形模型困住了一样，就这样一直卡一直卡。
然后突然我有了个足以让我通过easy版本的想法，那就是我们可以不光单看某一个点，我们可以格局打开! 我们一列一列地看，如果dp一列一列地进行转移的话，那他肯定是能满足无后效性的，因为当前列的状态百分之一百不会受到后面列的影响，因为他压根就不能往左边走，所以有时候想这种DP还是得脑洞大开，一直盯着一个点想很容易就把自己搞进去了，如果你不跳出来那就一直卡到死，现在我就详细说一下一列一列地转移该怎么转移。
我现在画个图给大家看一下，方便大家更直观的理解
就假设我们现在3*3的矩阵，每个格子内代表其行下标和列下标（画的很丑抱歉），黑色格子代表我们已经确定好的状态，蓝色格子我们不用管，红色格子代表我们现在要求出的格子。
现在这个红格子，最重要的结论就是它的状态一定是从左侧三个点转移过来的，我们把左侧一列这三个点的情况取最大即可，
假设是从 [1,1] 转移过来，那么它一定是往右走一格再往下走一格，它的值就是 f[1][1]+a[2][2]+a[1][2] 。
假设是从 [2,1] 转移过来,那么它一定是直接往右走一格，它的值就是 f[2][1]+a[2][2] 。
假设是从 [3,1] 转移过来的，那么它一定是直接往右走一格到 [3,2] ，然后再往下走一格到 [1,2] ,然后再往下走一格到 [2,2] ，它的值就是 f[3][1]+a[3][2]+a[1][2]+a[2][2] ，
看到这里相信大家应该都差不多明白了，然后我们还需要定义一个sum数组， sum[i] 就代表从当前列的前 i 行的和为多少，这样子我们就得到了一个转移方程
if(j<i)
{
dp[i][o]=max(dp[i][o],dp[j][o-1]+sum[i]-sum[j-1]);
}
else if(j==i) dp[i][o]=max(dp[i][o],dp[i][o-1]+a[i][o]);
else if(j>i)
{
dp[i][o]=max(dp[i][o],dp[j][o-1]+sum[n]-sum[j-1]+sum[i]);
}
(非常抱歉还不会markdown的数学公式)
这里 [i,o] 就代表我们当前要求的状态的行下标和列下标，然后j代表的是当前列左侧一列的行下标， j 是个变量，j的值域就是 [1,n] ，n 就是题目中的行数。
这个方程大家可以套入我刚刚说的那个情况里，就正好能够对应上了，就是需要分成三个情况来进行转移，
如果 j < i ，就代表它是往右走一格，然后一直往下走直到到达 [i,o] ，
如果 j == i ，那就是直接往右边走一格到达 [i,o] ，
如果是 j > i ，那就是往右走一格，然后一直走到底，再传送回顶部，再往下走直到抵达 [i,o]
OK,我们几乎就要成功通过 easy 版本了，现在就差把初始状态给求出来了，也就是我们怎么求第一列的状态，我用的是笨办法，应该是有办法能直接转移的，但是我还是直接先把第一列给直接求出来了，第一列的最优状态其实是很好求的，因为我们是从 [s,1] 这个点开始进行操作，所以我们可以直接用 sum 数组去求，
对于第一列行下标大于 s 的点，其值就是 sum[i]-sum[s-1] ;
对于第一列行下标等于 s 的点，其值就是 sum[s]-sum[s-1] ;
对于第一列行下标小于 s 的点，得绕一下，先把s~n的和求出来，就是 sum[n]-sum[s-1] ，再加上前 i 项的值，最后的结果就是 sum[n]-sum[s-1]+sum[i] ;
代码如下:
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i][1];
for(int i=1;i<=n;i++)
{
if(i>s)
{
dp[i][1]=sum[i]-sum[s-1];
}
else if(i==s)
{
dp[i][1]=sum[s]-sum[s-1];
}
else if(i<s)
{
dp[i][1]=sum[n]-sum[s-1]+sum[i];
}
}
好了，完成了这一步，我们就大功告成了，当然，别忘了把dp数组初始化成负无穷大，
下面是easy版本的AC代码:
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define int long long
#define endl '\n'
using namespace std;
const int N = 510;
int sum[N];
int a[N][N];
int dp[N][N];
void solve()
{
int n,m,s,t;
cin>>n>>m>>s>>t;
for(int i=1;i<=n;i++)
{
for(int o=1;o<=m;o++)
{
cin>>a[i][o];
dp[i][o]=-1e18;
}
}
//求初始状态
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i][1];
for(int i=1;i<=n;i++)
{
if(i>s)
{
dp[i][1]=sum[i]-sum[s-1];
}
else if(i==s)
{
dp[i][1]=sum[s]-sum[s-1];
}
else if(i<s)
{
dp[i][1]=sum[n]-sum[s-1]+sum[i];
}
}
//求初始状态
for(int o=2;o<=m;o++)
{//第一层循环是列
for(int i=1;i<=n;i++)
{//第二层循环是行
for(int j=1;j<=n;j++) sum[j]=0;
for(int j=1;j<=n;j++) sum[j]=sum[j-1]+a[j][o];
for(int j=1;j<=n;j++)
{
if(j<i)
{
dp[i][o]=max(dp[i][o],dp[j][o-1]+sum[i]-sum[j-1]);
}
else if(j==i) dp[i][o]=max(dp[i][o],dp[i][o-1]+a[i][o]);
else if(j>i)
{
dp[i][o]=max(dp[i][o],dp[j][o-1]+sum[n]-sum[j-1]+sum[i]);
}
}
}
}
cout<<dp[t][m]<<endl;
}
signed main()
{
IOS;
int T=1;
// cin>>T;
while(T--) solve();
return 0;
}
（啊，我发现题解确实是不容易写啊，写到现在已经写了一个多小时了，继续，把hard版本也给搂了）
现在再看hard版本，我们发现hard版本的 n 和 m 变得更大了，这就要求我们要在 O(n^2) 左右的复杂度能够通过这道题，我们刚刚的方法必须还需要一层循环来进行转移，现在我们就要想办法把这一层循环给去掉。
说实话，我一开始有想过用线段树的方法快速地求出，想了想，不太行，然后我就开始仔细观察第三层循环，啊，盯着看了半节课(大学生),发现了一个关键的东西，还是假设我们当前要转移的点是 [i,o] ，我们现在要求是，如何快速得知左侧一列大于 i 的点中的最大值，也就是如何才能快速求出 j > i 的这种情况，然后我就发现它其实是可以预处理的，再来看一下 j > i 情况的转移方程
else if(j>i)
{
dp[i][o]=max(dp[i][o],dp[j][o-1]+sum[n]-sum[j-1]+sum[i]);
}
我们就发现了关键问题的关键，那就是 sum[i] 是固定的，因为你必须从顶上下来，我们现在只是不知道从哪个起点开始到 n 它的值最大，也就是说现在问题转化为了，预处理出 [i+1,n] 这个区间内
dp[i][o-1]+sum[n]-sum[i-1]的最大值
所以 sum[i] 和 [i+1,n] 区间求最大 这两部分完全可以剥离开来执行，使得我们的执行速度得到大大的提高，正如感情一样，也许分开会得到更好的结果(emo)
那就好说了啊，我们可以直接递推出来，再用一个数组记录就行，我们可以定义个数组，它就叫做 down ，其中 down[i] 的意思就是说，在 [i,n] 这段区间里，dp[i][o-1]+sum[n]-sum[i-1]的最大值，它的转移方法如下
for(int i=n;i>=1;i--) down[i]=max(down[i+1],sum[n]-sum[i-1]+dp[i][o-1]);
//注意它是逆着推出来的
所以在预处理出来之后，刚刚那段代码:
else if(j>i)
{
dp[i][o]=max(dp[i][o],dp[j][o-1]+sum[n]-sum[j-1]+sum[i]);
}
我们就可以改写成
dp[i][o]=max(dp[i][o],down[i+1]+sum[i]);
现在我们已经加速很多了，我们现在只需要再把 j < i 的这种情况优化掉，我们就可以得到一个时间复杂度允许的代码！让我们再来看看之前 j < i 情况的转移方程
if(j<i)
{
dp[i][o]=max(dp[i][o],dp[j][o-1]+sum[i]-sum[j-1]);
}
哇，我们惊喜的发现 sum[i] 也是个定值，让我们回忆一下这个 sum[i] 是干啥的，它代表的是我们 [1,i] 这个区间的和，求这个和是为了个 sum[j-1] 作差用的，这样我们才能求出 [j,i] 这个区间的和是多少。
那么由于这个 sum[i] 也是固定的，所以我们也可以把 dp[j][o-1]-sum[j-1] 的最大值预处理出来，让我们能快速得知 [1,i] 这个区间 dp[j][o-1]-sum[j-1] 的最大值，和刚刚同理，我们可以定义一个数组叫up，其中 up[i] 的意思就是 [1,i] 这个区间内， dp[i][o-1]-sum[j-1] 的最大值。
还要提一嘴就是这个 up 数组其实没有刚刚的 down 数组直观，因为它的意义比较抽象，主要原因就是 sum[i] 被剥离了，但是它在数学的意义上是肯定没问题的，不用在这个地方纠结太多。
up数组的转移方法如下：
for(int i=1;i<=n;i++) up[i]=max(up[i-1],dp[i][o-1]-sum[i-1]);
这样子我们刚刚
if(j<i)
{
dp[i][o]=max(dp[i][o],dp[j][o-1]+sum[i]-sum[j-1]);
}
这个老转移方程，在我们递推出up数组之后，就可以非常爽的改写成下面这样：
dp[i][o]=max(dp[i][o],up[i]+sum[i]);
啊，最耗时间的两种情况都被我们狠狠优化掉了，那么相等的情况怎么说？就是 j == i 这种情况，hhh我最后才发现它其实已经被 up 的情况给包含了，因为我们最开始的那个转移方程，这种情况其实也是可以被包含在 j < i 这种情况里的，我们回看一下
else if(j==i) dp[i][o]=max(dp[i][o],dp[i][o-1]+a[i][o]);
//这里的a[i][o]实际上就等于sum[i]-sum[j-1];
所以我们其实已经全部OK了，还有一些细节就是down和up数组是要初始化的，
down是 [1,n+1] 初始化为-1e18
up是 [0,n] 初始化为-1e18
至于为啥是这个范围大家等会儿看到我完整的代码就明白了
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define int long long
#define endl '\n'
using namespace std;
const int N = 2e3 + 10;
int up[N];
int down[N];
int sum[N];
int a[N][N];
int dp[N][N];
void solve()
{
int n,m,s,t;cin>>n>>m>>s>>t;
for(int i=1;i<=n;i++)
for(int o=1;o<=m;o++) cin>>a[i][o];
for(int i=1;i<=n;i++)
for(int o=1;o<=m;o++) dp[i][o]=-1e18;
//求初始状态
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i][1];
for(int i=1;i<=n;i++)
{
if(i>s)
{
dp[i][1]=sum[i]-sum[s-1];
}
else if(i==s)
{
dp[i][1]=sum[s]-sum[s-1];
}
else if(i<s)
{
dp[i][1]=sum[n]-sum[s-1]+sum[i];
}
}
//求初始状态
for(int o=2;o<=m;o++)
{
for(int i=1;i<=n;i++) sum[i]=0;
for(int i=1;i<=n+1;i++) down[i]=-1e18;
for(int i=0;i<=n;i++) up[i]=-1e18;
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i][o];
for(int i=n;i>=1;i--) down[i]=max(down[i+1],sum[n]-sum[i-1]+dp[i][o-1]);
for(int i=1;i<=n;i++) up[i]=max(up[i-1],dp[i][o-1]-sum[i-1]);
for(int i=1;i<=n;i++) dp[i][o]=max(down[i+1]+sum[i],up[i]+sum[i]);
}
cout<<dp[t][m]<<endl;
}
signed main()
{
IOS;
int T=1;
// cin>>T;
while(T--) solve();
return 0;
}
大家有什么问题可以在评论区留言问我。
京公网安备 11010502036488号