Steven_Meng's Blog

传送门

这道题把坑设在了数据范围里面，第一眼看上去没有思路，第二眼发现$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();
    }
}