P1436棋盘分割 记忆化搜索解法

P1436棋盘分割

前缀和一下。
直接记忆化搜索（每次切割后只能选择一边继续切）

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

typedef long long ll;
const ll MAXN = 1e6+10;
const ll INF = 0x3f3f3f3f3f3f3f3f;

ll N, M, g[10][10], s[10][10], f[10][10][10][10][20];

ll dfs(ll, ll, ll, ll, ll);
ll get(ll, ll, ll, ll);

int main() {
    scanf("%lld", &N);
    for (ll i = 1; i <= 8; i++) {
        for (ll j = 1; j <= 8; j++) {
            scanf("%lld", &g[i][j]);
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + g[i][j];
        }
    }
    N--;
    printf("%lld", dfs(1, 1, 1, 8, 8));
    return 0;
}

ll dfs(ll tim, ll x1, ll y1, ll x2, ll y2) {
    if (f[x1][y1][x2][y2][tim]) return f[x1][y1][x2][y2][tim];
    if (tim > N) return get(x1, y1, x2, y2);
    ll ret = INF; //f[x1][y1][x2][y2][tim];
    for (ll i = x1; i < x2; i++) {
        ret = min(ret, get(x1, y1, i, y2) + dfs(tim+1, i+1, y1, x2, y2));
        ret = min(ret, get(i+1, y1, x2, y2) + dfs(tim+1, x1, y1, i, y2));
    }
    for (ll i = y1; i < y2; i++) {
        ret = min(ret, get(x1, y1, x2, i) + dfs(tim+1, x1, i+1, x2, y2));
        ret = min(ret, get(x1, i+1, x2, y2) + dfs(tim+1, x1, y1, x2, i));
    }
    f[x1][y1][x2][y2][tim] = ret;
    return ret;
}

ll get(ll x1,ll y1,ll x2,ll y2) {
    ll kk = s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1];
	return kk * kk;
}