0922考试T4 区间DP

0922考试T4

题目描述：

机房所有的电脑构成了一个(n*n)的矩阵，每一台电脑都有一个便利值(a[i][j])，在这个矩形里找两个互不重叠的矩形，并且这两个矩形的便利值之和为(p)的倍数，问对多可以选出多少个电脑。

区间DP。

我们先对每行求一个前缀和。然后用(l, r)从纵方向框住一部分，(g[l])表示在(l)右边的最大矩形，(f[r])表示紧贴着(r)并且在(r)左边的最大矩形。

而且我们可以知道，如果左右区间相同，上界为1，下界不同的两个矩形，他们的便利值对(p)取模后相同，说明这两个矩形的下界框住的这个矩形的便利值一定是(p)的倍数。

然后把矩形顺时针反转一下再做一遍相同操作就好了。

#include <bits/stdc++.h>

using namespace std;

inline long long read() {
    long long s = 0, f = 1; char ch;
    while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
    for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
    return s * f;
}

const int N = 305;
int n, p, tmp, ans;
int a[N][N], f[N], g[N], sum[N][N], tong[55];

void clear() {
    memset(f, 0, sizeof(f)); 
    memset(g, 0, sizeof(g));
    memset(sum, 0, sizeof(sum));
}

void calc() {
    clear();
    for(int i = 1;i <= n; i++) 
        for(int j = 1;j <= n; j++) sum[i][j] = sum[i][j - 1] + a[i][j];
    
    for(int len = 1;len <= n; len ++) {
        for(int l = 1;l + len - 1 <= n; l++) {
            int r = l + len - 1;
            memset(tong, -1, sizeof(tong)); tong[0] = 0;
            int tmp = 0;
            for(int i = 1;i <= n; i++) {
                tmp += sum[i][r] - sum[i][l - 1];
                tmp %= p;
                if(tong[tmp] == -1) tong[tmp] = i;
                else {
                    g[l] = max(g[l], (i - tong[tmp]) * len);
                    f[r] = max(f[r], (i - tong[tmp]) * len);
                }
            }
        }
    }
    for(int i = n - 1;i >= 1; i--) g[i] = max(g[i], g[i + 1]);
    for(int i = 1;i <= n - 1; i++) ans = max(ans, f[i] + g[i + 1]);
}

void turn() {
    int tmp[N][N];
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= n; j++) tmp[i][j] = a[i][j];
    
    for(int i = 1;i <= n; i++) 
        for(int j = 1;j <= n; j++) a[i][j] = tmp[j][i];
}

int main() {

    freopen("matrix.in","r",stdin); freopen("matrix.out","w",stdout);

    n = read(); p = read();
    for(int i = 1;i <= n; i++) 
        for(int j = 1;j <= n; j++) a[i][j] = read();

    calc(); turn(); calc();

    printf("%d", ans);

    fclose(stdin); fclose(stdout);
    return 0;
}
/*
5 6
7 2 3 1 1
5 0 6 0 0
8 6 6 5 3
4 3 7 8 2
4 0 0 6 9
*/