三角符号
符号三角形
Description
+ + - + - + + //第一行有n个符号，2个同号下面是“+”，异号下面是“-”
+ - - - - + //左图有14个“+”，14个“-”，给定n，求“+”“-”个数相同的符号
- + + + - //三角形个数
- + + -
- + -
- -
+Input
输入n （1 < n ≤ 23）
Output
输出不同方案的个数
Sample Input
3
Sample Output
4
Solution
dfs
可以发现，当第一行字符确定了以后，整个三角形就确定了。枚举第一行， 如果每次都要建立整个三角形再数，显然会T。剪枝：最先想到，如果当前数的“+”或“-”已经大于总数的一半，剪掉；如果当前数目加上剩余的全部数目仍小于总数的一半，剪掉；可以考虑，如果能将当前数过的状态保存下来，不用重复数相似的状态，可以优化很多。可以发现，第一行每增加一个符号，只会影响最右边斜着的一排符号，而不会影响之前构造的部分，根据此特性剪枝，每次只要数最右边一列的符号即可。
Code
#include <cstdio> #include <cstring> #include <algorithm> #define maxn 100005 #define INF 0x3f3f3f3f typedef long long ll; using namespace std; int n, dig[25][25], ans; void dfs(int tmp, int sum, int k) { if (tmp > sum) return; if (tmp + n*(n+1)/2 - (k-1)*k/2 < sum) return; if (k > n){ if (tmp == sum) ans++; return; } int now = 0; for (int i = 0; i <= 1; i++){ dig[1][k] = i; now = i; for (int j = 2; j <= k; j++){ dig[j][k - j + 1] = dig[j - 1][k - j + 1] ^ dig[j - 1][k - j + 2]; now += dig[j][k - j + 1]; } dfs(tmp + now, sum, k + 1); } } int main() { scanf("%d", &n); int sum = (n*(n+1)/2); if (sum & 1){ printf("0\n"); return 0; } sum /= 2; dfs(0, sum, 1); printf("%d\n", ans); return 0; }
相关阅读
在Excel中录入数据的时候经常需要录入一些带平方的数据，或许有的朋友不会用打平方符号，对于新手来说还是有一定难度，怎么办?接下来是
2019独角兽企业
$符号在php中是表示变量的特征字符， 在js中它也有很多作用， 一般我们用来命名一个函数名称，获取id的1、首先可以用来表示变量， 比如
使用css画个等腰直角三角形： 可以使用border来进行绘制，具体见注释 <!DOCTYPE html> <html lang="en"> <head> <meta charset=
无法解析的外部符号 "class google::protobuf::inter
无法解析的外部符号 "class google::protobuf::internal::ExplicitlyConstructed<class std::basic_string<char,struct std::cha