天天看點

uva 10755(dp)

題意:有a*b*c個小長方體塊組成一個大長方體塊,每個小長方體有一個對應數值,問大長方體的子長方體數值之和最大是多少。

題解:想不出來、、看書上說是枚舉上下邊界,然後将問題轉化成一維問題,但是書上的代碼看不懂,然後看了某大神題解後,腦海裡大概yy了下立體圖形還是比較好了解的。注意s[i][j][k]存了從一個角到i、j、k的總共數值和。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 30;
long long s[N][N][N];

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int a, b, c;
        memset(s, 0, sizeof(s));
        scanf("%d%d%d", &a, &b, &c);
        for (int i = 1; i <= a; i++)
            for (int j = 1; j <= b; j++)
                for (int k = 1; k <= c; k++) {
                    scanf("%lld", &s[i][j][k]);
                    s[i][j][k] += s[i][j][k - 1] + s[i][j - 1][k] + s[i - 1][j][k] + s[i - 1][j - 1][k - 1] - s[i - 1][j][k - 1] - s[i - 1][j - 1][k] - s[i][j - 1][k - 1] ;
                }
        long long res = -9999999999999;
        for (int x1 = 0; x1 < a; x1++)//枚舉上下界
            for (int x2 = x1 + 1; x2 <= a; x2++)
                for (int y1 = 0; y1 < b; y1++)//枚舉二維空間的行
                    for (int y2 = y1 + 1; y2 <= b; y2++) {
                        long long temp = 0;
                        for (int z = 1; z <= c; z++) { //枚舉列
                            long long S = (s[x2][y2][z] - s[x1][y2][z]) - (s[x2][y1][z] - s[x1][y1][z]);
                            res = max(res, S - temp);
                            temp = min(temp, S);
                        }
                    }
        printf("%lld\n", res);
        if (t)
            printf("\n");
    }
    return 0;
}