C11CUT - Cắt bảng
Tác giả: flashmt
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int f[1 << 16], a[4][4], m, n;
int dp(int mask)
{
if (!mask) return 0;
int &res = f[mask];
if (res >= 0) return res;
res = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (mask >> (i * n + j) & 1)
{
// horizontal
int x = a[i][j], usedMask = 1 << (i * n + j);
res = max(res, dp(mask - usedMask) + x);
for (int k = j + 1; k < n; k++)
if (mask >> (i * n + k) & 1)
{
x = x * 10 + a[i][k]; usedMask += 1 << (i * n + k);
res = max(res, dp(mask - usedMask) + x);
}
else break;
// vertical
x = a[i][j]; usedMask = 1 << (i * n + j);
for (int k = i + 1; k < m; k++)
if (mask >> (k * n + j) & 1)
{
x = x * 10 + a[k][j]; usedMask += 1 << (k * n + j);
res = max(res, dp(mask - usedMask) + x);
}
}
return res;
}
int main()
{
memset(f, -1, sizeof(f));
cin >> m >> n;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
cin >> a[i][j];
cout << dp((1 << (m * n)) - 1) << endl;
}