快乐的70分暴力搜索

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10;
const int MAXM = 10;
int n, m, ans;
int cntAns[MAXN * MAXM + 5];
int cnt[MAXN + 5][MAXM + 5]; // 每个位置被几只马踩了
int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};
void dfs(int x, int y, int now)
{
    // 棋盘看完了
    if (x > n + 1)
    {
        ans = max(ans, now);
        cntAns[now]++;
        return;
    }
    int xx, yy; // 下一个位置
    yy = y + 1;
    if (yy > m + 1)
        xx = x + 1, yy = 2;
    else
        xx = x;
    // 当前位置不放马
    dfs(xx, yy, now);
    // 当前位置能放马的话就试试看放个马
    if (!cnt[x][y])
    {
        for (int i = 0; i < 8; i++)
            cnt[x + dx[i]][y + dy[i]]++;
        dfs(xx, yy, now + 1);
        for (int i = 0; i < 8; i++)
            cnt[x + dx[i]][y + dy[i]]--;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    // 棋盘从 (2,2) ~ (n+1,m+1)
    // 用到了 (0,0) ~ (n+3,m+3)
    dfs(2, 2, 0);
    cout << ans << " " << cntAns[ans] << "\n";
    return 0;
}

由此可以改的快乐打表程序

    for (n = 1; n <= 10; n++)
        for (m = n; m <= 10; m++)
        {
            ans = 0;
            memset(cntAns, 0, sizeof(cntAns));
            // 棋盘从 (2,2) ~ (n+1,m+1)
            // 用到了 (0,0) ~ (n+3,m+3)
            dfs(2, 2, 0);
            cout << n << " " << m << " " << ans << " " << cntAns[ans] << "\n";
        }

然后就可以赌一赌规律了

我跑了 $10$ 分钟左右，跑到了 7 8 28 2 的位置。

...
4 4 8 6
4 5 10 3
4 6 12 3
4 7 14 3
4 8 16 3
4 9 18 3
4 10 20 3
5 5 13 1
5 6 15 2
5 7 18 1
5 8 20 2
5 9 23 1
5 10 25 2
6 6 18 2
6 7 21 2
6 8 24 2
6 9 27 2
6 10 30 2
7 7 25 1
7 8 28 2

如果考场机子比较差，可以根据 $5~7$ 的情况赌一赌 qx 说的那个规律。

    cin >> n >> m;
    if (n > m)
        swap(n, m);
    if (n < 5)
    {
        // 棋盘从 (2,2) ~ (n+1,m+1)
        // 用到了 (0,0) ~ (n+3,m+3)
        dfs(2, 2, 0);
        cout << ans << " " << cntAns[ans] << "\n";
    }
    else
    {

        if (n % 2 == 1 && m % 2 == 1)
            cout << n * m / 2 + 1 << " " << 1 << "\n";
        else
            cout << n * m / 2 << " " << 2 << "\n";
    }

qx 说的第二种做法那个减枝非常妙！