https://atcoder.jp/contests/abc163
E - Active Infants
题意：有n个孩子从1排到n，每个孩子有权值，要求重排一次，每个孩子的快乐度为他的权值乘他移动的距离，要求所有孩子的快乐度之和最大。
dp
首先要发现先分配权值大的孩子更优，因为第一个分配的和第二个分配的孩子移动距离的差最大只有1，那么如果先分配权值小的，他的移动距离最多只会增多1，显然是不如先分配大的。
而当分配一个孩子时，显然是要把它往两边分配。
所以策略就是按照权值从大到小按顺序分配，每次向两边分配。
然后就是类似区间dp的部分了。
dp[i][j] 表示左边分配了i个，右边分配了j个，最大快乐和。
i+j=已分配的孩子数；更新分配到左边或右边。
注意这里并没有固定分割线，所以最终取答案时要遍历分割线取最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1);
const ll mod = 1e9 + 7;
int n, c[N], cnt[N], siz[N];
ll cal(int x) {
return 1ll * x*(x - 1) / 2 + x;
}
ll ans[N];
vector<int>G[N];
void dfs(int u, int _fa) {
siz[u] = 1;
int tmp = cnt[c[u]];
for (int v : G[u]) {
if (v == _fa)continue;
cnt[c[u]] = 0;
dfs(v, u);
siz[u] += siz[v];
ans[c[u]] += cal(siz[v] - cnt[c[u]]);
}
cnt[c[u]] = tmp + siz[u];
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)scanf("%d", &c[i]);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1, 0);
for (int i = 1; i <= n; i++) {
printf("%lld\n", cal(n) - ans[i] - cal(n - cnt[i]));
}
return 0;
}
|
F - path pass i
题意：给定一棵树，每个节点有颜色，对于每种颜色，问有多少种路径经过至少一个这个颜色的节点。
考虑反面，不经过该颜色的路径数。
路径数等于C(n,2)，所以只要找在一起的非该颜色节点，整棵树被该颜色节点分成几部分，要找到每一部分的结点数。
cnt[i] 记录颜色为i的节点的子树结点数。
dfs每次进入子节点之前要清空当前节点颜色的计数器，以便得到子节点的子树中的该颜色节点子树大小。u减去子节点中该颜色节点的子树大小就是夹在两个该颜色节点之间的节点个数。
注意u的不同子节点要分开算，所以计算答案应该是在遍历子节点的同时。
最后更新u的颜色的子树大小。跳出到上一层计算。
主要是对dfs的理解不够。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1);
const ll mod = 1e9 + 7;
int n, c[N], cnt[N], siz[N];
ll cal(int x) {
return 1ll * x*(x - 1) / 2 + x;
}
ll ans[N];
vector<int>G[N];
void dfs(int u, int _fa) {
siz[u] = 1;
int tmp = cnt[c[u]];
for (int v : G[u]) {
if (v == _fa)continue;
cnt[c[u]] = 0;
dfs(v, u);
siz[u] += siz[v];
ans[c[u]] += cal(siz[v] - cnt[c[u]]);
}
cnt[c[u]] = tmp + siz[u];
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)scanf("%d", &c[i]);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1, 0);
for (int i = 1; i <= n; i++) {
printf("%lld\n", cal(n) - ans[i] - cal(n - cnt[i]));
}
return 0;
}
|
