「Bzoj 1084」「SCOI2005」最大子矩阵 (DP+前缀和)

发表于 | 分类于 | | + s

Bzoj 1084
$m$只有$1, 2$，分情况讨论：
$m=1​$时，就是一个简单的最大连续子段和，设$dp(i,j)​$为前$i​$个数分了$j​$段的最优值
则有$dp(i,j)=max(dp(i-1, j), dp(k,j-1)+S_{i}-S_{k})$，其中$S$是前缀和。
$m=2$时，我们设$dp(i,j,k)​$为第一列前$i$个数第二列前$j$个数分了$k$个矩阵的最优值
则$dp(i,j,k)=max(dp(i-1,j,k), dp(i,j-1,k), dp(l, j, k-1)+S1_i - S1_l, $
$dp(i, l, k-1)+S2_i - S2_l)$，其中$S1$是第一列前缀和，$S2$是第二列前缀和。
当$i=j$时，还可以选择两列一起的大矩阵，则$dp(i,j,k)=max(dp(l,l,k-1)+S1_i+S2_j-S1_l-S2_l)$
初始都要赋值为$-INF$，但是当$j=0$时要赋值为$0$，不然就会导致答案负数。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100 + 5, MAXK = 10 + 5, INF = 1000000000;
int n, m, k, dp1[MAXN][MAXK], dp2[MAXN][MAXN][MAXK], s1[MAXN], s2[MAXN];
void clean() {
    s1[0] = s2[0] = 0;
}
void solve() {
    clean();
    if (m == 1) {
        for (int i=0;i<=n;i++) {
            for (int j=1;j<=k;j++) {//1开始，否则没有初值了 
                dp1[i][j] = -INF;
            }
        }
        for (int i=1;i<=n;i++) {
            int x;
            scanf("%d", &x);
            s1[i] = s1[i - 1] + x;
        }
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=k;j++) {
                dp1[i][j] = dp1[i - 1][j];//不选 
                for (int i1=0;i1<i;i1++) {
                    dp1[i][j] = max(dp1[i][j], dp1[i1][j - 1] + s1[i] - s1[i1]);
                }
            }
        }
        printf("%d\n", dp1[n][k]);
    } else {
        for (int i=0;i<=n;i++) {
            for (int j=0;j<=n;j++) {
                for (int l=1;l<=k;l++) {//1开始，否则没有初值了 
                    dp2[i][j][l] = -INF;
                }
            }
        }
        for (int i=1;i<=n;i++) {
            int x, y;
            scanf("%d%d", &x, &y);
            s1[i] = s1[i - 1] + x;
            s2[i] = s2[i - 1] + y;
        }
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=n;j++) {
                for (int l=1;l<=k;l++) {
                    dp2[i][j][l] = max(dp2[i - 1][j][l], dp2[i][j - 1][l]);//不选 
                    for (int i1=0;i1<i;i1++) dp2[i][j][l] = max(dp2[i][j][l], dp2[i1][j][l - 1] + s1[i] - s1[i1]);
                    for (int j1=0;j1<j;j1++) dp2[i][j][l] = max(dp2[i][j][l], dp2[i][j1][l - 1] + s2[j] - s2[j1]);
                    if (i == j) {//可以选两排一起的一个大矩阵 
                        for (int ij=0;ij<min(i, j);ij++) dp2[i][j][l] = max(dp2[i][j][l], dp2[ij][ij][l - 1] + s1[i] + s2[j] - s1[ij] - s2[ij]);
                    }
                }
            }
        }
        printf("%d\n", dp2[n][n][k]);
    }
}
int main() {
    #ifndef ONLINE_JUDGE 
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    scanf("%d%d%d", &n, &m, &k), solve();
    return 0;
}
------ 本文结束 ------