题目链接

• Equation
  • 注意到等式x+y=z中每个字母只能是一位正整数。
  • 本地预处理所有形如x+y=z的所有可能情况，共有36种。
  • 枚举这36种等式出现与否，同时更新答案。
  • 剪枝：若当前枚举到第i个等式且得到的个数为cnt，如果cnt+36-i<ans，说明再枚举下去数量也不会超过已有的最大值，应该立刻停止。

代码：

#include<cstdio>
using namespace std;
const int inf=0x3f3f3f3f;
const int combination[36][3]={{1,1,2},{1,2,3},{1,3,4},{1,4,5},{1,5,6},{1,6,7},{1,7,8},{1,8,9},{2,1,3},{2,2,4},{2,3,5},{2,4,6},{2,5,7},{2,6,8},{2,7,9},
{3,1,4},{3,2,5},{3,3,6},{3,4,7},{3,5,8},{3,6,9},{4,1,5},{4,2,6},{4,3,7},{4,4,8},{4,5,9},{5,1,6},{5,2,7},{5,3,8},{5,4,9},
{6,1,7},{6,2,8},{6,3,9},{7,1,8},{7,2,9},{8,1,9}};
int digits[10],cnt,ans;
void dfs(int i)
{
	if(cnt+36-i<=ans)
	{
		return;
	}
	if(i==36)
	{
		if(cnt>ans)
		{
			ans=cnt;
		}
		return;
	}
	if(digits[combination[i][2]]&&((combination[i][0]==combination[i][1]&&digits[combination[i][0]]>1)||(combination[i][0]!=combination[i][1]&&digits[combination[i][0]]&&digits[combination[i][1]])))
	{
		++cnt;
		--digits[combination[i][0]];
		--digits[combination[i][1]];
		--digits[combination[i][2]];
		dfs(i+1);
		++digits[combination[i][0]];
		++digits[combination[i][1]];
		++digits[combination[i][2]];
		--cnt;
	}
	dfs(i+1);
}
int main()
{
	int T,kcase=0;
	scanf("%d",&T);
	while(T--)
	{
		for(int i=1;i<=9;++i)
		{
			scanf("%d",&digits[i]);
		}
		ans=0;
		dfs(0);
		printf("Case #%d: %d\n",++kcase,ans);
	}
	return 0;
}