沙雕贪心......
我一开始想的是倒着来，每次减去一个。
然后我们就有两个决策：去掉最后一个/去掉前面某一个。
然后第一个决策用并查集维护，第二个决策用线段树即可。仔细想想觉得普及组不会考这种东西，慌得一批。
然后又发现可能有问题：你可能取x个的时候不从x + 1转移过来，而是x + 2
然后就不会了。
然后看提解发现正解是顺着来......什么沙雕。
结论：若取x个的时候最优解是集合S，那么取x+1个时的最优解集合一定包含S。(说明了上面我的做法是对的)
证：
即证对于每一个取x+1的方案p，若不包含S，都可以找到一个包含S的方案比它更优。
设取x个的最优方案为r
考虑最右那一个：
①p的最后那个等于r的最右那一个时，前面我们随便去掉一个不与r配对的位置d，然后p一定还与r不同。
我们把p调整成r，然后加上d，这样就比原来的p更优了。
②p的最后那个小于r的最后那一个时，我们同样去掉一个d，然后调整，最后加上d，就会更优。
③p的最后那个大于r的最后那个时，把p的最后那个去掉，同时p的价值减去（2 * 从r最后到p最后的距离）。
这样就相当于情况①中去掉d之后的p了。
然后调整成r之后把原来p的最后加上，再加上减去的价值，就会比原来的p更优。
#include <cstdio>
#include <algorithm>
#include <queue> const int N = ; int a[N], x[N], g[N];
std::priority_queue<int> Q; int main() {
int n;
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%d", &x[i]);
x[i] <<= ;
}
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
} for(int i = n; i >= ; i--) {
if(x[i] + a[i] > x[g[i + ]] + a[g[i + ]]) {
g[i] = i;
}
else {
g[i] = g[i + ];
}
} int now = g[]; int ans = a[now] + x[now], pos = ;
printf("%d\n", ans); for(int i = ; i <= n; i++) {
while(pos < now) {
Q.push(a[pos]);
pos++;
}
if(pos == now) {
pos++;
}
if(!Q.empty() && Q.top() > a[g[now + ]] + x[g[now + ]] - x[now]) {
ans += Q.top();
Q.pop();
}
else {
ans -= x[now];
now = g[now + ];
ans += a[now] + x[now];
}
printf("%d\n", ans);
} return ;
}
AC代码
然后我又打了一开始那个线段树的想法......
#include <cstdio>
#include <algorithm>
#include <queue> const int N = , INF = 0x3f3f3f3f; int a[N], x[N], ans[N];
int small[N << ], fa[N]; int find(int x) {
if(fa[x] == x) {
return x;
}
return fa[x] = find(fa[x]);
} inline void pushup(int o) {
int ls = o << ;
int rs = ls | ;
if(a[small[ls]] <= a[small[rs]]) {
small[o] = small[ls];
}
else {
small[o] = small[rs];
}
return;
} void build(int l, int r, int o) {
if(l == r) {
small[o] = r;
return;
}
int mid = (l + r) >> ;
build(l, mid, o << );
build(mid + , r, o << | );
pushup(o);
return;
} int ask(int L, int R, int l, int r, int o) {
if(L <= l && r <= R) {
return small[o];
}
int mid = (l + r) >> ; if(R <= mid) {
return ask(L, R, l, mid, o << );
}
if(mid < L) {
return ask(L, R, mid + , r, o << | );
} int as = ask(L, R, l, mid, o << );
int t = ask(L, R, mid + , r, o << | );
if(a[t] < a[as]) {
as = t;
}
return as;
} void change(int p, int l, int r, int o) {
if(l == r) {
a[r] = INF;
return;
}
int mid = (l + r) >> ;
if(p <= mid) {
change(p, l, mid, o << );
}
else {
change(p, mid + , r, o << | );
}
pushup(o);
return;
} int main() {
int n, sum = ;
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%d", &x[i]);
x[i] <<= ;
}
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
fa[i] = i;
sum += a[i];
}
sum += x[n];
ans[n] = sum; build(, n, ); int now = n;
for(int i = n - ; i >= ; i--) {
int pos = ask(, now - , , n, );
if(a[now] + x[now] - x[find(now - )] > a[pos]) {
sum -= a[pos];
change(pos, , n, );
fa[pos] = find(pos - );
}
else {
sum -= (a[now] + x[now] - x[find(now - )]);
now = find(now - );
}
ans[i] = sum;
} for(int i = ; i <= n; i++) {
printf("%d\n", ans[i]);
}
return ;
}
AC代码
话说这个代码我调都没调，一次就写对了。