提交记录：R200626982

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int cntc[20];
int ans = -1;
int row[20][20];
int col[20][20];
int box[20][20];

struct node
{
	int a, v, c, b;
	
	bool operator < (const node & b) const
	{
		return cntc[c] > cntc[b.c];
	}
} ;

node p[20][20];

int val[20][20] = {
	{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
	{0, 6, 6, 6, 6, 6, 6, 6, 6, 6}, 
	{0, 6, 7, 7, 7, 7, 7, 7, 7, 6}, 
	{0, 6, 7, 8, 8, 8, 8, 8, 7, 6}, 
	{0, 6, 7, 8, 9, 9, 9, 8, 7, 6}, 
	{0, 6, 7, 8, 9, 10, 9, 8, 7, 6}, 
	{0, 6, 7, 8, 9, 9, 9, 8, 7, 6}, 
	{0, 6, 7, 8, 8, 8, 8, 8, 7, 6}, 
	{0, 6, 7, 7, 7, 7, 7, 7, 7, 6}, 
	{0, 6, 6, 6, 6, 6, 6, 6, 6, 6}
};

int BOX[20][20] = {
	{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
	{0, 1, 1, 1, 4, 4, 4, 7, 7, 7}, 
	{0, 1, 1, 1, 4, 4, 4, 7, 7, 7}, 
	{0, 1, 1, 1, 4, 4, 4, 7, 7, 7}, 
	{0, 2, 2, 2, 5, 5, 5, 8, 8, 8}, 
	{0, 2, 2, 2, 5, 5, 5, 8, 8, 8}, 
	{0, 2, 2, 2, 5, 5, 5, 8, 8, 8}, 
	{0, 3, 3, 3, 6, 6, 6, 9, 9, 9}, 
	{0, 3, 3, 3, 6, 6, 6, 9, 9, 9}, 
	{0, 3, 3, 3, 6, 6, 6, 9, 9, 9}
};

int cal()
{
	int ret = 0;
	for (int i = 1; i <= 9; i++)
		for (int j = 1; j <= 9; j++)
			ret += p[i][j].a * p[i][j].v;
	return ret;
}

void dfs(int x, int y)
{
	// cout << x << " " << y << endl;
	if (y > 9)
	{
		ans = max(ans, cal());
		return ;
	}
	if (p[x][y].a)
	{
		if (row[x][p[x][y].a])
			return ;
		if (col[y][p[x][y].a])
			return ;
		if (box[BOX[x][y]][p[x][y].a])
			return ;
		row[x][p[x][y].a] = 1;
		col[y][p[x][y].a] = 1;
		box[p[x][y].b][p[x][y].a] = 1;
		int nx = x + 1, ny = y;
		if (nx > 9) ny++, nx = 1;
		dfs(nx, ny);
		row[x][p[x][y].a] = 0;
		col[y][p[x][y].a] = 0;
		box[p[x][y].b][p[x][y].a] = 0;
	}
	else
	{
		for (int i = 1; i <= 9; i++)
		{
			if (row[x][i])
				continue ;
			if (col[y][i])
				continue ;
			if (box[p[x][y].b][i])
				continue ;
			p[x][y].a = i;
			row[x][i] = 1;
			col[y][i] = 1;
			box[p[x][y].b][i] = 1;
			int nx = x + 1, ny = y;
			if (nx > 9) ny++, nx = 1;
			dfs(nx, ny);
			p[x][y].a = 0;
			row[x][i] = 0;
			col[y][i] = 0;
			box[p[x][y].b][i] = 0;
		}
	}
}

int main()
{
	for (int i = 1; i <= 9; i++)
		for (int j = 1; j <= 9; j++)
		{
			cin >> p[i][j].a;
			p[i][j].v = val[i][j];
			p[i][j].c = j;
			p[i][j].b = BOX[i][j];
			if (p[i][j].a) cntc[j]++;
		}
	for (int i = 1; i <= 9; i++)
		sort(p[i] + 1, p[i] + 9 + 1);
	dfs(1, 1);
	cout << ans << endl;
	return 0;
}

我的做法是暴力考虑每一种情况，优化是先填已知数字最多的列，但是只得了五分，求各位大神的帮助。