某大型纪录片（P14169 题解）

· · 题解

这题一看就是动态规划。

我们设 f_{i,j,k} 表示某老师在第 i 分钟时站在第 j 名同学身后，所用的体力为 k 时，前 i 分钟所产生的最大总怒气值。

根据题意可以直接写出 DP 式子，具体怎么推出来的不再赘述：

f_{i,j,k}=\max_{p=\max(-k,-j+1)}^{\min(k,n-j)} f_{i-1,j+p,k-|p|}+q_{i,j}

其中 q_{i,j} 是某老师第 i 分钟时站在第 j 名同学身后所增加的怒气值。

初始条件为 f_{0,j,0}=0，其中 j\in [1,n]。但好像和直接 memset(f,0,sizeof f); 没什么区别。

最终答案是 \max_{j=1}^n \max_{k=0}^T f_{m,j,k}。

:::info[什么你还不会求 q]{open} 很简单，根据题意，就是让你求区间和，借助前缀和即可。

代码：

for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++)
        sum[i][j]=sum[i][j-1]+a[i][j];
for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++)
        q[i][j]=sum[i][min(n,j+X)]-sum[i][max(1,j-X)-1];

:::

当然这样的 DP 时间复杂度 \mathcal O(mn^2T)，一定会 \textcolor{#052242}{\text{TLE}} 的。

我们可以利用七年级知识把原式转换成下面这样：

f_{i,j,k}=\max(\max_{p=0}^{\min(k,n-j)} f_{i-1,j+p,k-p},\max_{p=0}^{\min(k,j-1)} f_{i-1,j-p,k-p})+q_{i,j}

可以发现，原式的计算主要涉及

\max_{p=0}^{\min(k,n-j)} f_{i-1,j+p,k-p},\max_{p=0}^{\min(k,j-1)} f_{i-1,j-p,k-p}

两部分。

我们设：

s_{i,j,k}=\max_{p=0}^{\min(k,n-j)} f_{i,j+p,k-p}

我们发现，s_{i,j,k} 所统计的答案包含所有 s_{i,j+1,k-1} 所统计的答案。于是我们希望用 s_{i,j+1,k-1} 推出 s_{i,j,k}，就有了下面式子：

s_{i,j,k}=\max(s_{i,j+1,k-1},f_{i,j,k})

初始条件为 \begin{cases} s_{i,n,k}=f_{i,n,k} \\ s_{i,j,0}=f_{i,j,0} \end{cases}。

同理我们设：

t_{i,j,k}=\max_{p=0}^{\min(k,j-1)} f_{i,j-p,k-p}

则也有：

t_{i,j,k}=\max(t_{i,j-1,k-1},f_{i,j,k})

初始条件为：

t_{i,1,k}=f_{i,1,k} \\ t_{i,j,0}=f_{i,j,0} \end{cases}

上述所有的 i\in [1,m],j\in [1,n],k\in [0,T]。

那 f 的 DP 式为：

f_{i,j,k}=\max(s_{i-1,j,k},t_{i-1,j,k})+q_{i,j}

就这样，我们用 \mathcal O(mnT) 的时间复杂度出色地完成了本题。

好像没有什么问题了吧……于是我们写完了代码，自信一交：

程序在 \text{64MB} 里撞出闷响，数组的影子漫过了内存的墙。记录里的 \textcolor{#052242}{\text{MLE}} 像道锁，困住了我高深算法的光。

哦，忘了，空间复杂度也是 \mathcal O(mnT)，而这题的内存限制还是 \text{64MB}。

不过我们分析了 f,s,t 的第一维下标 i，发现它看似没有用处，实则是个累赘，拖着内存的后腿，于是我们果断删掉它。

DP 式就变成了：

f_{j,k}=\max(s_{j,k},t_{j,k})+q_{i,j}

当我们把新的代码交上去的那一瞬间，绿色的 \textcolor{#52C41A}{\text{AC}} 跃上屏幕，好像整个世界都在欢呼。

我们以 \mathcal O(mnT) 的时间复杂度，\mathcal O(nT) 的空间复杂度通过了本题。

代码：

#include<iostream>
#include<cstring>
using namespace std;
const int N=315;
int f[N][N],a[N][N],q[N][N],sum[N][N],s[N][N],t[N][N];
int n,m,X,T;
int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') f=(c=='-'?-1:f),c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}
void solve(){
    n=read(),m=read(),X=read(),T=read();
    memset(f,0,sizeof f);
    memset(sum,0,sizeof sum);
    memset(q,0,sizeof q);
    memset(s,0,sizeof s);
    memset(t,0,sizeof t);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=read();
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            sum[i][j]=sum[i][j-1]+a[i][j];
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            q[i][j]=sum[i][min(n,j+X)]-sum[i][max(1,j-X)-1];
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++)
            for(int k=0;k<=T;k++)
                f[j][k]=max(s[j][k],t[j][k])+q[i][j];
        for(int j=n;j>=1;j--)//这里一定要倒序枚举！！！
            for(int k=0;k<=T;k++){
                if(j==n) s[j][k]=f[j][k];
                else if(k==0) s[j][k]=f[j][k];
                else s[j][k]=max(s[j+1][k-1],f[j][k]);
            }
        for(int j=1;j<=n;j++)
            for(int k=0;k<=T;k++){
                if(j==1) t[j][k]=f[j][k];
                else if(k==0) t[j][k]=f[j][k];
                else t[j][k]=max(t[j-1][k-1],f[j][k]);
            }
    }
    int answ=0;
    for(int j=1;j<=n;j++)
        for(int k=0;k<=T;k++)
            answ=max(answ,f[j][k]);
    printf("%d\n",answ);
}
signed main(){
    int Csdsl;Csdsl=read();//CeShiDianShuLiang
    while(Csdsl--) solve();
    return 0;
}