https://www.luogu.com.cn/problem/P8293
题解
题意转化:
将括号序列建成一棵树,操作1相当于把一个点和它的儿子都挂到同一深度的另一个点下面,操作2相当于表示同一深度的点不用管顺序,最后要求的就是把这棵树变成一条链的最小代价.
分类讨论:
-
\(x = 0, y = 0\)
答案为\(0\).
-
\(x = 0, y = 1\)
每一层的答案为\(sum\)(这一层点的权值和)减去留下的点的权值.
策略就是留下权值最大的点,用\(multiset\)维护即可.
-
\(x = 1, y = 1\)
可以分两种情况讨论.
如果留下的是权值最小的点,那么直接把其它点挂在权值最小的点的下面即可.答案为\(sum\)加上最小值乘\(sz - 2\).
如果留下的不是权值最小的点,那么先把其它点挂到最小值的下面,最后再把最小值挂到留下的那个点的下面,答案还是\(sum\)加上最小值乘\(sz - 2\).
策略还是每次留下最大值,还是可以用\(multiset\)维护.
-
\(x = 1, y = 0\)
假设当前留下的点的权值为\(val\),使用同样的策略,这一层的答案为\(val\)加上最小值乘\(sz - 2\).每一层的答案似乎不好单独计算,但是可以考虑总贡献.可以发现最后只有一个点的\(val\)不会被加,那个点会被放到最后一层.
是不是所有点都能被放到最后一层?
不是的,刚开始的一长段\(sz = 1\)的层是不能移动的.而对于\(sz > 2\)的层可以考虑把非最大值和非最小值留下来.
最后的\(sz\)会形如\(1,1\cdots 1,2,2\cdots2,> 2,> 2,\cdots > 2,2,1\).
也就是说,前面的一长段\(2\)最后只会下传出\(1\)个值,且贡献为这一段的所有的数的和减下传出的那个值,相当于最小值对它们没有贡献,因为\(sz - 2 = 0(sz = 2)\).
所以,我们可以只考虑下传出的那个值和剩下的所有值.可以发现,下传值有两种影响,把它传到第\(n\)层,或让它贡献一段最小值.
对于需要传到第\(n\)层的,它不可能产生最小的贡献,选最大的即可.
对于需要贡献最小值的,选一个最小的值下传即可.
综上,只需要选择一个最小值和一个最大值下传,再对答案取\(min\)即可,可以做到线性.
总结
考试的时候简单地认为选定一个点作为这一层的点之后,只需要把其它点移到它下面就行了,于是推出了一个错误的公式.
这是贪心策略的问题,是我思考不够全面的体现.
对于分类情况很少的题目,不要先想着得到一个通解,要分类讨论.
代码
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int inf = 1e9;
const int maxn = 800005;
int n, top1, top2, id[maxn];
int v[3], depth[maxn], cnt[maxn];
ll a[maxn], mn[maxn], mx[maxn];
int stk1[maxn], stk2[maxn], indeg[maxn];
char s[maxn];
vector<int> e[maxn];
void dfs(int u, int from) {
depth[u] = depth[from] + 1;
for(int i = 0; i < (int)e[u].size(); i++) {
int v = e[u][i];
dfs(v, u);
}
}
vector<int> p[maxn];
multiset<int> st;
// v[1] = 0 v[2] = 1
void solve1() {
ll ans = 0, sum = 0;
for(int i = 1; i < n; i++) {
for(int j : p[i]) {
sum = sum + a[j];
st.insert(a[j]);
}
auto it = st.end();
it--;
sum = sum - *it;
ans = ans + sum;
st.erase(it);
}
cout << ans << '\n';
}
// v[1] = 1 v[2] = 1
void solve2() {
ll ans = 0, sum = 0;
for(int i = 1; i < n; i++) {
for(int j : p[i]) {
sum = sum + a[j];
st.insert(a[j]);
}
ans = ans + sum + (ll)(st.size() - 2) * (*st.begin());
auto it = st.end();
it--;
sum = sum - *it;
st.erase(it);
}
cout << ans << '\n';
}
// v[1] = 1 v[2] = 0
void solve3() {
cnt[0] = 1;
for(int i = 1; i <= n; i++)
cnt[i] = cnt[i - 1] + (int)p[i].size() - 1;
int l = 1, r = 1;
while(l <= n && cnt[l] == 1)
l++, r++;
while(r <= n && cnt[r] == 2)
r++;
for(int i = 0; i <= n; i++) {
mn[i] = inf;
mx[i] = -inf;
}
ll sum = 0;
for(int i = l; i < n; i++) {
if(i != r) {
mn[i] = mn[i - 1];
mx[i] = mx[i - 1];
}
for(int j : p[i]) {
mn[i] = min(mn[i], a[j]);
mx[i] = max(mx[i], a[j]);
sum = sum + a[j];
}
}
ll ans1 = sum - mx[n - 1], ans2 = sum - max(mx[n - 1], mx[r - 1]);
for(int i = r; i < n; i++) {
ans1 = ans1 + min(mn[i], mn[r - 1]) * (cnt[i] - 2);
ans2 = ans2 + mn[i] * (cnt[i] - 2);
}
cout << min(ans1, ans2) << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> v[1] >> v[2];
cin >> (s + 1);
for(int i = 1; i <= n; i++)
cin >> a[i];
if(v[1] == 0 && v[2] == 0) {
cout << "0\n";
return 0;
}
int tot = 0;
for(int i = 1; i <= n + n; i++) {
if(s[i] == '(') {
id[i] = ++tot;
stk1[++top1] = i;
}
else {
while(top2 && stk1[top1] < stk2[top2]) {
e[id[stk1[top1]]].push_back(id[stk2[top2]]);
indeg[id[stk2[top2]]]++;
top2--;
}
stk2[++top2] = stk1[top1];
top1--;
}
}
for(int i = 1; i <= n; i++)
if(!depth[i] && !indeg[i])
dfs(i, 0);
for(int i = 1; i <= n; i++)
p[depth[i]].push_back(i);
if(v[1] == 0 && v[2] == 1)
solve1();
else if(v[1] == 1 && v[2] == 1)
solve2();
else
solve3();
return 0;
}