T1. 数字三角形问题

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。

时间限制：1 s
内存限制：64 MB

• 输入
  输入的第一行是一个整数 $N(1<N\le 100)$，给出三角形的行数。
  下面的 $N$ 行给出数字三角形。数字三角形上的数的范围都在 $0$ 和 $100$ 之间。
• 输出
  输出最大的和。
• 样例输入

  5
  7
  3 8
  8 1 0 
  2 7 4 4
  4 5 2 6 5
  

• 样例输出

  30
  

思路分析

此题考查动态规划，属于基础题。

定义 $f_{i,j}$ 表示从 $(1,1)$ 走到 $(i,j)$ 的路径最大和，不难得出状态转移方程为 f i , j = max ⁡ { f i − 1 , j − 1 , f i − 1 , j } f_{i,j} = \max\{f_{i-1,j-1}, f_{i-1,j}\} fi,j​=max{fi−1,j−1​,fi−1,j​}。最终在第 $n$ 行找到最大值即为答案，事实上，因为所有元素非负，可以在动规过程中求解最大值。

/** Name: T1.cpp* Problem: 数字三角形问题* Author: Teacher Gao.* Date&Time: 2024/12/10 15:41*/#include <iostream>using namespace std;inline int max(int a, int b) { return a > b ? a : b; }int main()
{ios::sync_with_stdio(false);cin.tie(0);int n, a[105][105], f[105][105] = {0}, ans = 0;cin >> n;for (int i = 1; i <= n; i++)for (int j = 1; j <= i; j++)cin >> a[i][j];for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {f[i][j] = max(f[i-1][j-1], f[i-1][j]) + a[i][j];ans = max(ans, f[i][j]);}}cout << ans << endl;return 0;
}

T2. 大盗

阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。

这条街上一共有 $N$ 家店铺，每家店中都有一些现金。阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。

作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？

时间限制：1 s
内存限制：64 MB

• 输入
  输入的第一行是一个整数 $T(T\le 50)$，表示一共有 $T$ 组数据。
  接下来的每组数据，第一行是一个整数 $N(1\le N\le 100,000)$，表示一共有 $N$ 家店铺。第二行是 $N$ 个被空格分开的正整数，表示每一家店铺中的现金数量。每家店铺中的现金数量均不超过 $1000$。
• 输出
  对于每组数据，输出一行。该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金数量。
• 样例输入

  2
  3
  1 8 2
  4
  10 7 6 14
  

• 样例输出

  8
  24
  

• 提示
  对于第一组样例，阿福选择第 $2$ 家店铺行窃，获得的现金数量为 $8$。
  对于第二组样例，阿福选择第 1 1