这题有两种做法：

第一种是，我们小数据搜索一下，发现当$n,m$都稍微比较大的时候，如果$n,m$都是奇数，能放$(nm+1)/2$个，一种方案，否则能放$nm/2$个，两种方案。然后直接小数据搜索，大数据直接输出答案即可。

第二种是，我们对于$i=1,2,...,n$依次进行搜索，记录对于一个理想情况下的$i\times m$的格子，最多能放多少个马，一旦当前放的加上未来理想情况下能放的个数不比最优答案优秀，就剪枝，也可以很快通过。

#include <bits/stdc++.h>
#define maxn 20 
using namespace std;
int n,m;
int vis[maxn][maxn];
int zd[maxn];
int best,ans=0;
int dx[8]={-1,-1,-2,-2,1,1,2,2};
int dy[8]={-2,2,1,-1,2,-2,1,-1};
int can(int x,int y)
{
	if (vis[x][y]) return 0;
	return 1;
}
void put(int x,int y,int t)
{
	vis[x][y]+=t;
	for (int f=0;f<=7;f++)
	if (x+dx[f]>=1 && x+dx[f]<=n && y+dy[f]>=1 && y+dy[f]<=m)
		vis[x+dx[f]][y+dy[f]]+=t;
	return;
}

void dfs(int x,int y,int now)
{
	if (x==n+1) 
	{
		if (now>best) {best=now; ans=1;}
		else if (now==best) ans++;
		return;
	}
	int lef=zd[n-x]+(m-y+1);
	if (now+lef<best) return; 
	int nx=x,ny=y+1; if (ny==m+1) ny=1,nx++;
	dfs(nx,ny,now);
	if (can(x,y))
	{
		put(x,y,1);
		dfs(nx,ny,now+1);
		put(x,y,-1);
	}
}
int main()
{
	cin>>n>>m; int N=n;
	for (int i=1;i<=N;i++)
	{
		best=ans=0; n=i;
		dfs(1,1,0);
		zd[i]=best;
	}
	cout<<best<<" "<<ans<<endl;
}

快乐的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 说的第二种做法那个减枝非常妙！