题目。
看一下特殊性质，考虑 dp。
设 \(dp_{i,j,z}\) 表示李老师在第 \(i\) 分钟站在 \(j\) 后体力为 \(z\) 的最大怒气值。
\[\operatorname{calc}(i,j,x) = \sum_{t= \max (1,j-x)}^{min(n,j+x)}a_{i,t}
\]
则有 \(dp_{i,j,z}= \max (dp_{i-1,la,z-|j-la| }+\operatorname{calc}(i,j,x)),la \in [1,n]\)。
时间是 \(O(N^4)\) 的，空间是 \(O(N^3)\) 的，发现转移只用到了前面的值于是滚动优化到 \(O(N^2)\)，时间继续优化转移。
\[dp_{i,j,z}= (\max dp_{i-1,la,z-|j-la| })+\operatorname{calc}(i,j,x),la \in[1,n]
\]
\(\operatorname{calc}(i,j,x)\) 可以前缀和优化掉，然后去绝对值。
\[dp_{i,j,z}=
\begin{cases}
(\max dp_{i-1,la,z-j+la })+\operatorname{calc}(i,j,x),la \le j \\(\max dp_{i-1,la,z+j-la })+\operatorname{calc}(i,j,x),la \ge j \\
\end{cases}
\]
考虑预处理前缀和后缀。
设 \(pr_{i,v,j}=\max dp_{i-1,la,v+la},la \le j\)（\(v\) 表示 \(z-j\)），
\(suf_{i,v,j}=\max dp_{i-1,la,v-la},la \ge j\)（\(v\) 表示 \(z+j\)）。
则 \(dp_{i,j,z}= \max (pr_{i,z-j,j},suf_{i,z+j,j})+\operatorname{calc}(i,j,x)\)。
最后时间复杂度为 \(O(N^3)\)。
注意 \(pr\) 的下标可能为负数要加偏移量，以及一些边界问题。
code
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,r,l) for(int i=(r);i>=(l);--i)const int N=305;
int n,m,x,k,a[N][N],dp[2][N][N],pr[N<<1][N],suf[N<<1][N];
int calc(int i,int b,int x){return a[i][min(b+x,n)]-a[i][max(0,b-x-1)];}
void solve(){cin>>n>>m>>x>>k;int now=1;rep(i,1,m) rep(j,1,n) cin>>a[i][j],a[i][j]+=a[i][j-1];memset(dp,0,sizeof dp);memset(pr,0,sizeof pr);memset(suf,0,sizeof suf);const int ad=n;rep(i,1,m){now^=1;memset(dp[now],0,sizeof dp[now]);rep(j,1,n)rep(z,0,k)dp[now][j][z]=max(pr[z-j+ad][j],suf[z+j][j])+calc(i,j,x);rep(zj,-n,k)rep(la,1,n){if(zj+la>k||zj+la<0) continue;pr[zj+ad][la]=max(dp[now][la][zj+la],pr[zj+ad][la-1]);}rep(zj,1,n+k)per(la,n,1){if(zj-la<0||zj-la>k) continue;suf[zj][la]=max(dp[now][la][zj-la],suf[zj][la+1]);}}int ans=0;rep(j,1,n) rep(z,0,k) ans=max(ans,dp[now][j][z]);cout<<ans<<'\n';
}
int main(){cin.tie(0)->ios::sync_with_stdio(false);int T=1;cin>>T;while(T--) solve();
}