密码脱落
来源： 第七届蓝桥杯省赛C++A/C组,第七届蓝桥杯省赛JAVAC组
题目要求
题目描述：
X 星球的考古学家发现了一批古代留下来的密码。
这些密码是由 A 、 B 、 C 、 D 四种植物的种子串成的序列。
仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。
由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。
你的任务是：
给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。
输入格式：
共一行，包含一个由大写字母 A B C D 构成的字符串，表示现在看到的密码串。
输出格式：
输出一个整数，表示至少脱落了多少个种子。
数据范围：
输入字符串长度不超过1000
输入样例1：
ABCBA
输出样例1：
0
输入样例2：
ABDCDCBABC
输出样例2：
3
思路分析
代码
#include <cstdio> #include <string.h> const int N = 1010; char s[N]; int f[N][N]; int main() { scanf("%s", s); int n = strlen(s); for (int len = 1; len <= n; len ++ ) for (int l = 0; l + len - 1 < n; l ++ ) { int r = l + len - 1; if (len == 1) f[l][r] = 1; else { if (s[l] == s[r]) f[l][r] = f[l + 1][r - 1] + 2; if (f[l][r - 1] > f[l][r]) f[l][r] = f[l][r - 1]; if (f[l + 1][r] > f[l][r]) f[l][r] = f[l + 1][r]; } } printf("%d\n", n - f[0][n - 1]); return 0; }
生命之树
来源： 第六届蓝桥杯省赛C++B组,第六届蓝桥杯省赛JAVAB组
题目要求
题目描述：
输入格式：
输出格式：
输出一行一个数，表示上帝给这棵树的分数。
数据范围：
输入样例：
5 1 -2 -3 4 5 4 2 3 1 1 2 2 5
输出样例：
8
思路分析
代码
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; const int N = 100010, M = N * 2; int n; int w[N]; int h[N], e[M], ne[M], idx; LL f[N]; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; } void dfs(int u, int father) { f[u] = w[u]; for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (j != father) { dfs(j, u); f[u] += max(0ll, f[j]); } } } int main() { scanf("%d", &n); memset(h, -1, sizeof h); for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]); for (int i = 0; i < n - 1; i ++ ) { int a, b; scanf("%d%d", &a, &b); add(a, b), add(b, a); } dfs(1, -1); LL res = f[1]; for (int i = 2; i <= n; i ++ ) res = max(res, f[i]); printf("%lld\n", res); return 0; }
