1 条题解
-
0
#include <bits/stdc++.h> using namespace std; int e[512345][2]; int tot = 0; string s; //dp_max[i][j] 节点 i 染成 j 色后,最多多少个绿。 //0 绿、1 红、2 蓝、 int dp_max[512345][3]; int dp_min[512345][3]; void dfs_build(int now) { tot++; if (s[now - 1] == '1') { e[now][0] = tot + 1; dfs_build(tot + 1); } if (s[now - 1] == '2') { e[now][0] = tot + 1; dfs_build(tot + 1); e[now][1] = tot + 1; dfs_build(tot + 1); } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> s; dfs_build(1); for (int i = tot; i >= 1; i--) { int l = e[i][0]; int r = e[i][1]; if (!l) { dp_max[i][0] = dp_min[i][0] = 1; dp_max[i][1] = dp_min[i][1] = 0; dp_max[i][2] = dp_min[i][2] = 0; } else if (!r) { dp_max[i][0] = max(dp_max[l][1], dp_max[l][2]) + 1; dp_max[i][1] = max(dp_max[l][0], dp_max[l][2]); dp_max[i][2] = max(dp_max[l][0], dp_max[l][1]); dp_min[i][0] = min(dp_min[l][1], dp_min[l][2]) + 1; dp_min[i][1] = min(dp_min[l][0], dp_min[l][2]); dp_min[i][2] = min(dp_min[l][0], dp_min[l][1]); } else { dp_max[i][0] = max(dp_max[l][1] + dp_max[r][2], dp_max[l][2] + dp_max[r][1]) + 1; dp_max[i][1] = max(dp_max[l][0] + dp_max[r][2], dp_max[l][2] + dp_max[r][0]); dp_max[i][2] = max(dp_max[l][0] + dp_max[r][1], dp_max[l][1] + dp_max[r][0]); dp_min[i][0] = min(dp_min[l][1] + dp_min[r][2], dp_min[l][2] + dp_min[r][1]) + 1; dp_min[i][1] = min(dp_min[l][0] + dp_min[r][2], dp_min[l][2] + dp_min[r][0]); dp_min[i][2] = min(dp_min[l][0] + dp_min[r][1], dp_min[l][1] + dp_min[r][0]); } } cout << max(max(dp_max[1][0], dp_max[1][1]), dp_max[1][2]) << " " << min(min(dp_min[1][0], dp_min[1][1]), dp_min[1][2]) << "\n"; return 0; }
- 1
信息
- ID
- 3397
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 4
- 标签
- 递交数
- 2
- 已通过
- 2
- 上传者