P2331 [SCOI2005]最大子矩阵

传送门

这道题把坑设在了数据范围里面，第一眼看上去没有思路，第二眼发现 $m \le 2$ ，思路瞬间来了。

分情况讨论，分为 $m=1$ 情况和 $m=2$ 的情况。

声明，为了简略，我们设 $sum(l,r)$ 为 $\sum_{i=l}^{r}a[i]$ ， $sum1(l,r)$ 为 $\sum_{i=l}^r=a[0][i]$ ， $sum2(l,r)$ 同理

$m=1$

这个 $dp$ 方程比较容易，设 $dp[i][j]$ 为搞到第 $i$ 个数，总共 $j$ 段的最大和。发现第 $i$ 个数可选可不选， $dp[i-1][j]$ 为不选的情况。

方程为 $dp[i][j]=\max(dp[i-1][j],dp[k-1][j]+sum(k,i))$

$m=2$

考虑这个 $dp$ 方程，设 $dp[i][j][p]$ 为第一行搞到第 $i$ 个数，第二行搞到第 $j$ 个数，总共 $p$ 个矩阵，的最大和。

考虑每次可以从第一行转移一个 $1$ 行的矩阵，第二行转移一个 $1$ 行的矩阵，也可以从两行一起转移一个 $2$ 行的矩阵，也可以什么都不转移。

考虑什么都不转移： $dp[i][j][p]=\max (dp[i-1][j][p],dp[i][j-1][p])$

考虑转移第一行： $dp[i][j][p]=\max(dp[l][j][p-1]+sum1(l+1,j))(l \in [0,i))$ ，第二列同理

转移第一行的情况：

转移第二行的情况：

注意，标成蓝色代表这里 $dp$ 做完，并不代表全部选择，标成红色代表全部选择

考虑转移两行，只有在 $i==j$ 的时候才有这种转移，因为 $2$ 行的矩阵把状态一波推平，推出 $dp[i][i][p]=\max (dp[l][l][p-1]+sum1(l+1,i)+sum2(l+1,i) ) (l \in [0,i))$

#include <bits/stdc++.h>
#define sum1(l,r) (s1[(r)]-s1[(l)-1])
#define sum2(l,r) (s2[(r)]-s2[(l)-1])
#define MAXN 105
#define MAXK 15
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
inline void chkmax(int &x,int y){
    if (x<y) x=y;
}
int n,m,k;
namespace Solve1{
    int a[MAXN];
    int dp[MAXN][MAXK];
    inline int Solve(){
        for (register int i=1;i<=n;++i){
            a[i]=read();
        }
        for (register int p=1;p<=k;++p){
            for (register int i=1;i<=n;++i){
                dp[i][p]=dp[i-1][p];
                int sum=0;
                for (register int j=i;j>=1;--j){
                    sum+=a[j];
                    chkmax(dp[i][p],dp[j-1][p-1]+sum);
                }
            }
        }
        printf("%d\n",dp[n][k]);
        return 0;
    }
}
namespace Solve2{
    int a[2][MAXN];
    int s1[MAXN],s2[MAXN];
    int dp[MAXN][MAXN][MAXK];
    //第一行搞到i第二行搞到j总共k个矩形
    inline int Solve(){
        for (register int i=1;i<=n;++i){
            s1[i]=s1[i-1]+read();
            s2[i]=s2[i-1]+read();
        }
        for (register int p=1;p<=k;++p){
            for (register int i=1;i<=n;++i){
                for (register int j=1;j<=n;++j){
                    dp[i][j][p]=max(dp[i-1][j][p],dp[i][j-1][p]);//可以什么也不搞
                    if (i==j){//可以2个2个地推进
                        for (register int l=0;l<i;++l){
                            chkmax(dp[i][j][p],dp[l][l][p-1]+sum1(l+1,i)+sum2(l+1,j));
                        }
                    }
                    for (register int l=0;l<i;++l){
                        chkmax(dp[i][j][p],dp[l][j][p-1]+sum1(l+1,i));
                    }
                    for (register int l=0;l<j;++l){
                        chkmax(dp[i][j][p],dp[i][l][p-1]+sum2(l+1,j));
                    }
                }
            }
        }
        printf("%d\n",dp[n][n][k]);
        return 0;
    }
}
int main(){
    n=read(),m=read(),k=read();
    if (m==1){
        return Solve1::Solve();
    }
    else {
        return Solve2::Solve();
    }
}