ลูกเกดบนแผ่นช็อกโกแลต: ลำดับการหั่นไม่มีผล สิ่งเดียวที่ต้องจำคือขอบสี่ด้านของบล็อก

#include <bits/stdc++.h>
using namespace std;
int n, m;
int pre[51][51];           // pre[i][j] = ลูกเกดรวมของแถว 0..i-1 คอลัมน์ 0..j-1
int dp[50][50][50][50];    // dp[r1][c1][r2][c2] = ค่าแรงน้อยสุดของบล็อกแถว r1..r2 คอลัมน์ c1..c2

// ลูกเกดในบล็อก ได้ในจังหวะเดียวด้วยผลรวมสะสมสองมิติ
int raisins(int r1, int c1, int r2, int c2){
    return pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1];
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++){
            int x; scanf("%d", &x);
            pre[i+1][j+1] = pre[i][j+1] + pre[i+1][j] - pre[i][j] + x;
        }
    // ไล่บล็อกจากเล็กไปใหญ่ บล็อกสูง h กว้าง w ใช้แค่บล็อกที่เล็กกว่ามันเสมอ
    for(int h = 1; h <= n; h++)
        for(int w = 1; w <= m; w++)
            for(int r1 = 0; r1 + h <= n; r1++)
                for(int c1 = 0; c1 + w <= m; c1++){
                    int r2 = r1 + h - 1, c2 = c1 + w - 1;
                    if(h == 1 && w == 1){ dp[r1][c1][r2][c2] = 0; continue; }   // ชิ้นเดี่ยว ไม่ต้องหั่นแล้ว
                    int best = INT_MAX;
                    for(int k = r1; k < r2; k++)   // หั่นแนวนอน ใต้แถว k
                        best = min(best, dp[r1][c1][k][c2] + dp[k+1][c1][r2][c2]);
                    for(int k = c1; k < c2; k++)   // หั่นแนวตั้ง ทางขวาของคอลัมน์ k
                        best = min(best, dp[r1][c1][r2][k] + dp[r1][k+1][r2][c2]);
                    dp[r1][c1][r2][c2] = best + raisins(r1, c1, r2, c2);
                }
    printf("%d\n", dp[0][0][n-1][m-1]);
}

#include <bits/stdc++.h>
using namespace std;
int n, m, g[7][7];
int memo[7][7][7][7];   // -1 แปลว่าบล็อกนี้ยังไม่เคยคิด

// ค่าแรงน้อยสุดของบล็อกแถว r1..r2 คอลัมน์ c1..c2
int solve(int r1, int c1, int r2, int c2){
    if(r1 == r2 && c1 == c2) return 0;                 // ชิ้นเดี่ยว ไม่ต้องหั่นแล้ว
    int &res = memo[r1][c1][r2][c2];
    if(res != -1) return res;                          // บล็อกนี้เคยคิดไว้แล้ว
    int s = 0;                                          // นับลูกเกดตรง ๆ ทีละช่อง
    for(int r = r1; r <= r2; r++)
        for(int c = c1; c <= c2; c++) s += g[r][c];
    int best = INT_MAX;
    for(int k = r1; k < r2; k++) best = min(best, solve(r1, c1, k, c2) + solve(k+1, c1, r2, c2));
    for(int k = c1; k < c2; k++) best = min(best, solve(r1, c1, r2, k) + solve(r1, k+1, r2, c2));
    return res = s + best;
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++) scanf("%d", &g[i][j]);
    memset(memo, -1, sizeof memo);
    printf("%d\n", solve(0, 0, n-1, m-1));
}

// ตัวตรวจ ไม่เชื่อว่าแต่ละบล็อกคิดแยกกันได้
// สถานะคือถุงของบล็อกที่ยังต้องหั่นทั้งหมด แล้วลองทุกบล็อก ทุกเส้น ทุกลำดับ
#include <bits/stdc++.h>
using namespace std;
typedef array<int,4> Blk;   // r1, c1, r2, c2
int n, m, g[4][4];
map<vector<Blk>, int> seen;

int raisins(const Blk &b){
    int s = 0;
    for(int r = b[0]; r <= b[2]; r++)
        for(int c = b[1]; c <= b[3]; c++) s += g[r][c];
    return s;
}

int best(vector<Blk> bag){
    if(bag.empty()) return 0;
    sort(bag.begin(), bag.end());
    auto it = seen.find(bag);
    if(it != seen.end()) return it->second;
    int res = INT_MAX;
    for(size_t i = 0; i < bag.size(); i++){
        Blk b = bag[i];
        vector<Blk> rest = bag;
        rest.erase(rest.begin() + i);
        vector<pair<Blk,Blk>> cuts;
        for(int k = b[0]; k < b[2]; k++) cuts.push_back({{b[0], b[1], k, b[3]}, {k+1, b[1], b[2], b[3]}});
        for(int k = b[1]; k < b[3]; k++) cuts.push_back({{b[0], b[1], b[2], k}, {b[0], k+1, b[2], b[3]}});
        for(auto &pc : cuts){
            vector<Blk> nb = rest;
            for(Blk x : {pc.first, pc.second})
                if(!(x[0] == x[2] && x[1] == x[3])) nb.push_back(x);   // ชิ้นเดี่ยวหลุดออกจากถุง
            res = min(res, raisins(b) + best(nb));
        }
    }
    return seen[bag] = res;
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++) scanf("%d", &g[i][j]);
    vector<Blk> start;
    if(n > 1 || m > 1) start.push_back({0, 0, n-1, m-1});
    printf("%d\n", best(start));
}