40pts求助#3 && #4 && #5 WA
查看原帖
40pts求助#3 && #4 && #5 WA
1050776
peterJr楼主2023/9/22 19:38

//测试详情,多谢!

#include <stdio.h> 

int num[10007] = {6, 2, 5, 5, 4, 5, 5, 3, 7, 6}, b[1007];
int cnt, n, vis[10007][10007];

void dfs(int k) {
	for (int i = 0; i <= 999; ++i) { //枚举i 
	  if (n - num[i] >= 0) { //如果火柴棒够用 
	    b[k] = i;
		n -= num[i];
		if (k == 3) { 
		  if (b[1] + b[2] == b[3] && ((!vis[b[1]][b[2]] && b[1] != b[2]) || (!vis[b[1]][b[2]] && !vis[b[2]][b[1]] && b[1] == b[2])) && n == 0) { //如果等式成立,等式不重复且火柴棒恰好用完 
		    cnt++; //计入方案总数 
		    if (b[1] != b[2]) vis[b[1]][b[2]] = 1; 
		    else vis[b[1]][b[2]] = 1, vis[b[2]][b[1]] = 1; //标记为用过的等式 
		    n += num[i];
		    return;
		  }
		} 
		else dfs(k + 1); //否则回溯 
		n += num[i]; //信息还原 
	  }
	}
}

int main() {
	scanf("%d", &n);
	n -= 4; //减去运算符“=”和“+”的火柴棍数量2+2=4 
	for (int i = 10; i <= 999; ++i) 
	  num[i] = num[i / 10] + num[i % 10]; //加入两位数火柴棍 
	dfs(1);
	printf("%d", cnt);
	return 0;
}
2023/9/22 19:38
加载中...