# 数字三角形

【问题描述】上图给出了一个数字三角形。从三角形的顶部到底部有很多条路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。

【输入格式】输入的第一行包含一个整数 N (1 ⩽ N ⩽ 100)，表示三角形的行数。下面的 N 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。

【输出格式】输出一个整数表示答案。

【样例输入】

3 8

8 1 0

2 7 4 4

4 5 2 6 5

【样例输出】 27

# 分析

转化成直角三角形，二维数组保存

# 代码

动态规划

	#include<bits/stdc++.h>
	using namespace std;
	const int N = 1e2 + 10;
	int n, a[N][N], dp[N][N];

	signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= i; j++) {
	cin >> a[i][j];
	}
	}

	dp[1][1] = a[1][1]; // 初始化顶部位置的最大路径和为其值
	for (int i = 2; i <= n; i++) {
	for (int j = 1; j <= i; j++) {
	dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + a[i][j]; // 计算当前位置的最大路径和
	}
	}

	// 根据 n - 1 的奇偶性输出：在满足向下走的次数与向右下走的次数相差不能超过 1 的条件下可能会到达的位置对应的 dp 值
	if ((n - 1) & 1)
	cout << max(dp[n][1 + (n - 1) / 2], dp[n][1 + (n - 1) / 2 + 1]) << '\n';
	else
	cout << dp[n][1 + (n - 1) / 2] << '\n';

	return 0;
	}

dfs

	#include<bits/stdc++.h>
	using namespace std;
	const int N = 1e2 + 10;
	int n, a[N][N], res[N][N];

	int dfs(int i, int j) {
	if (res[i][j]) return res[i][j];
	if (i == n) {
	if (n % 2 && j == n / 2 + 1) return a[i][j];
	if (n % 2 == 0 && (j == n / 2 \|\| j == n / 2 + 1)) return a[i][j];
	return -10000000; // 位置不正确时，返回一个极大的负数
	}
	return res[i][j] = max(dfs(i + 1, j), dfs(i + 1, j + 1)) + a[i][j];
	}

	signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= i; j++)
	cin >> a[i][j];

	cout << dfs(1, 1) << '\n';

	return 0;
	}

# 砝码称重

# 问题

【问题描述】你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1, W2, . . . , WN。请你计算一共可以称出多少种不同的重量。注意砝码可以放在天平两边。

【输入格式】输入的第一行包含一个整数 N。第二行包含 N 个整数：W1, W2, W3, . . . , WN。

【输出格式】输出一个整数表示答案。

【样例输入】

1 4 6

【样例输出】 10

【样例说明】能称出的 10 种重量是 123456791011。

1 = 1 2 = 6 − 4 (天平一边放 6，另一边放 4)

3 = 4 − 1

4 = 4

5 = 6 − 1

6 = 6

7 = 1 + 6

9 = 4 + 6 − 1

10 = 4 + 6

11 = 1 + 4 + 6

# 分析

，dp [i][j] 的含义为前 i 个砝码能否通过天平称出重量 j − offset

# 代码

	#include<bits/stdc++.h>
	using namespace std;
	const int N = 1e2 + 10, M = 1e5 + 10, offset = 1e5;
	int n, ans, w[N], dp[N][2 * M];

	signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
	cin >> w[i];

	dp[0][0 + offset] = true;
	for (int i = 1; i <= n; i++) {
	for (int j = 0; j < M + offset; j++) {
	if (j - w[i] >= 0)
	dp[i][j] \|= dp[i - 1][j - w[i]];
	dp[i][j] \|= dp[i - 1][j + w[i]] \| dp[i - 1][j];
	}
	}

	for (int i = 1 + offset; i < M + offset; i++)
	if (dp[n][i])
	ans++;

	cout << ans << '\n';

	return 0;
	}

# 括号序列

# 题目

【问题描述】给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法，当添加完成后，会产生不同的添加结果，请问有多少种本质不同的添加结果。两个结果是本质不同的是指存在某个位置一个结果是左括号，而另一个是右括号。例如，对于括号序列 ((()，只需要添加两个括号就能让其合法，有以下几种不同的添加结果：()()()、()(())、(())()、(()()) 和 ((()))。

【输入格式】输入一行包含一个字符串 s，表示给定的括号序列，序列中只有左括号和右括号。

【输出格式】输出一个整数表示答案，答案可能很大，请输出答案除以 1000000007 (即 109 + 7) 的余数。

【样例输入】 ((()

【样例输出】 5

# 分析

# 代码

	#include<bits/stdc++.h>
	#define int long long
	using namespace std;
	const int N = 5e3 + 10, mod = 1e9 + 7;
	string s;
	int dp[N][N], num[N], pre[N] , nex[N];

	// 计算方案数
	int calc(int need, bool flag)
	{
	if(!need) return 1; // 不需要添加括号也是一种方案
	memset(dp, 0, sizeof(dp));
	memset(num, 0, sizeof(num));
	memset(pre , 0 , sizeof(pre));
	memset(nex , 0 , sizeof(nex));
	//flag = 1 表示统计添加左括号的方案数；flag = 0 表示统计添加右括号的方案数（翻转）
	if(!flag) {
	reverse(s.begin(), s.end());
	for(int i = 0 ; i < s.size() ; i ++) {
	if(s[i] == ')') s[i] = '(';
	else s[i] = ')';
	}
	}
	int left = 0, cnt = 0;
	for(int i = 0 ; i < s.size() ; i ++) {
	if(s[i] == ')') num[++ cnt] = left; //cnt 为右括号的编号
	if(s[i] == '(') left ++; //left 表示原序列区间 [1,i] 的左括号的个数
	}
	// 区域 1 有左括号时 dp [1][0] = 1, 否则 dp [1][0] = 0
	if(num[1] > 0) dp[1][0] = 1 , pre[0] = 1;
	for(int i = 1 ; i <= cnt ; i ++) dp[1][i] = 1 , pre[i] = pre[i - 1] + 1;
	for(int i = 2 ; i <= cnt ; i ++){
	for(int j = 0 ; j <= need ; j ++) nex[j] = 0;
	for(int j = max(0ll , i - num[i]) ; j <= need ; j ++){
	dp[i][j] = pre[j];
	if(j - 1 < 0) nex[j] = dp[i][j];
	else nex[j] = (nex[j - 1] + dp[i][j]) % mod;
	}
	for(int j = 0 ; j <= cnt ; j ++) pre[j] = nex[j]; // 先用 nex [] 存储 dp [i-1] 的信息，再将 nex [] 的值赋给 pre []，这样下次循环 pre [] 存的值就是 dp [i-1] 的值
	}
	return dp[cnt][need];
	}

	signed main()
	{
	ios::sync_with_stdio(false);
	cin.tie(0) , cout.tie(0);
	cin >> s;
	int need = 0, pre = 0; //need 表示最少需要添加的左括号数，pre 表示序列前缀和
	for(int i = 0 ; i < s.size() ; i ++) {
	if(s[i] == '(') pre ++ ;
	else pre --;
	if(pre < 0) need ++, pre ++; //pre < 0 表示右括号数大于左括号数，此时需要添加左括号使得左括号数 >= 右括号数
	}
	int need2 = pre;
	cout << calc(need, 1) * calc(need2, 0) % mod << '\n';
	return 0;
	}

# 异或三角

# 题目

【问题描述】给定 T 个数 n1, n2, . . . , nT，对每个 ni 请求出有多少组 a, b, c 满足：（1）1 ⩽ a, b, c ⩽ ni；（2）a ⊕ b ⊕ c = 0，其中 ⊕ 表示二进制按位异或；（3）长度为 a, b, c 的三条边能组成一个三角形。

【输入格式】输入的第一行包含一个整数 T。接下来 T 行每行一个整数，分别表示 n1, n2, . . . , nT。

【输出格式】输出 T 行，每行包含一个整数，表示对应的答案。

【样例输入】

114514

【样例输出】 6 11223848130

# 分析

# 代码

动态规划

# 数字三角形

# 分析

# 代码

# 砝码称重

# 问题

# 分析

# 代码

# 括号序列

# 题目

# 分析

# 代码

# 异或三角

# 题目

# 分析

# 代码

字符串算法

数据结构