题意
一个长为 \(n\) 的排列，第 \(i\) 个位置上的数是 \(p_i\)；
花费 \(a_i\) 的代价将数字 \(i\) 移到任意位置；
花费 \(b_i\) 的代价将数字 \(i\) 移到左端；
花费 \(c_i\) 的代价将数字 \(i\) 移到右端。
问将排列从小到大排序的最小花费。
思路
首先有个贪心，就是 \(b_i,c_i\) 都要与 \(a_i\) 取 \(\min\)。
对于操作 \(B\)，一定是 \([1,x]\) 的数都进行操作；对于操作 \(C\)，一定是 \([y,n]\) 的数进行操作。
-
首先，如果我们要将 \(x\) 移到左边，那么 \(x\) 之前一直到 \(1\) 的数都必须要移动；
-
其次，操作 \(B\) 的代价是 \(\le\) 操作 \(A\) 的，因此一定是选择操作 \(B\) 更优。
-
对于操作 \(C\) 同理。
因此问题转化为：\([1,x]\) 移到左边，\([y,n]\) 移到右边，\([x+1,y-1]\) 一些不动，一些移到任意位置，要求代价最小。
我们设 \(f_i\) 表示 \(i\) 不动的最小花费（不含操作 \(C\)）。
那么有转移：
\[f_i=\min_{pos[j]<pos[i]}\{f_j+\sum_{k=j+1}^{i-1} a_k\} \]这个可以用树状数组优化。
代码
#include<bits/stdc++.h>
#define LL long long
#define max(x...) std::max({x})
#define min(x...) std::min({x})
#define FOR(i, x, y) for(int i = (x); i <= (y); i++)
#define ROF(i, x, y) for(int i = (x); i >= (y); i--)
inline int rd()
{
int sign = 1, re = 0; char c = getchar();
while(!isdigit(c)){if(c == '-') sign = -1; c = getchar();}
while(isdigit(c)){re = re * 10 + (c - '0'); c = getchar();}
return sign * re;
}
const LL INF = 1e18;
int n, p[200005];
int a[200005], b[200005], c[200005];
LL sa[200005], sb[200005], sc[200005];
LL tr[200005], f[200005];
inline int lb(int x) {return x & (-x);}
inline void add(int x, LL val)
{
x++;
while(x <= (n + 1))
{
tr[x] = min(tr[x], val);
x += lb(x);
}
}
inline LL query(int x)
{
x++; LL re = INF;
while(x)
{
re = min(re, tr[x]);
x ^= lb(x);
}
return re;
}
signed main()
{
#ifdef ONLINE_JUDGE
freopen("sort.in", "r", stdin);
freopen("sort.out", "w", stdout);
#endif
n = rd();
FOR(i, 1, n) p[rd()] = i;
FOR(i, 1, n) a[i] = rd(), b[i] = min(a[i], rd()), c[i] = min(a[i], rd());
FOR(i, 1, n) sa[i] = sa[i - 1] + a[i], sb[i] = sb[i - 1] + b[i], sc[i] = sc[i - 1] + c[i], tr[i] = INF;
tr[n + 1] = INF; add(0, 0);
LL ans = INF;
FOR(i, 1, n)
{
f[i] = min(query(p[i]) + sa[i - 1], sb[i - 1]);
ans = min(ans, f[i] + sc[n] - sc[i]);
add(p[i], f[i] - sa[i]);
}
printf("%lld", ans);
return 0;
}