P1021 · OFFICIAL SOLUTION

P1021 推翻暴政官方题解

Gioush OJ · P1021 推翻暴政

推翻暴政

【题意简述】

奇数个同伴按顺序到达渡口。每轮新到两人，与上一轮留下的一人组成三人，从中选两人过河，代价为二者时间最大值，最后剩下一人独自过河。求最小总代价。

【部分分】

每轮有三种选择，递归枚举可以得到指数复杂度。注意未来只与当前留下者有关，因此令状态表示当前轮结束后留下某人的最小附加代价，可以得到 $\mathcal{O}(n^2)$ DP。

【正解】

设当前加入的是 $a_{i-1},a_i$ ，旧状态留下者为 $x$ 。若让旧状态留下者继续留下，则本轮代价为 $\max(a_{i-1},a_i)$ ；若留下 $i-1$ ，则代价为 $\max(x,a_i)$ ；若留下 $i$ ，则代价为 $\max(x,a_{i-1})$ 。把每轮固定增加的 $\max(a_{i-1},a_i)$ 记作全局 Tag，剩余转移只需要维护 $f_x$ 与 $f_x+a_x$ 的区间最小值。对 $a_x\le v$ 和 $a_x>v$ 分别查询，即可用离散化线段树完成每轮转移。

【复杂度】

每轮两次查询、两次单点插入，时间复杂度为 $\mathcal{O}(n\log n)$ ，空间复杂度为 $\mathcal{O}(n)$ 。状态值与答案需要使用 long long。

【参考代码】

1#include <cstdio>2#include <cstring>3#include <algorithm>4#define MAXN 2000105#define LSon Node[Now].LeftSon6#define RSon Node[Now].RightSon7using namespace std;8const long long INF=10000000000000000;9 10int n,m,cnt=0,Line[MAXN],Mapping[MAXN];11long long Tag=0;12 13void Discrete() {sort(Mapping+1,Mapping+n+1);m=unique(Mapping+1,Mapping+n+1)-Mapping-1;return;}14int Find(int x) {return lower_bound(Mapping+1,Mapping+m+1,x)-Mapping;}15 16struct node {17    int l,r,LeftSon,RightSon;18    long long Min,MinSum;19}Node[MAXN<<2];20 21void Update(int Now) {Node[Now].Min=min(Node[LSon].Min,Node[RSon].Min);Node[Now].MinSum=min(Node[LSon].MinSum,Node[RSon].MinSum);return;}22 23int Build(int l,int r) {24    int Now=++cnt;25    Node[Now]={l,r,0,0,INF,INF};26    if (l==r) return Now;27    int Mid=(l+r)>>1;28    LSon=Build(l,Mid);RSon=Build(Mid+1,r);29    return Now;30}31 32void Modify(int Now,int Pos,long long Val) {33    if (Node[Now].l==Node[Now].r) {34        Node[Now].Min=min(Node[Now].Min,Val);35        Node[Now].MinSum=min(Node[Now].MinSum,Val+Mapping[Node[Now].l]);36        return;37    }38    int Mid=(Node[Now].l+Node[Now].r)>>1;39    if (Pos<=Mid) Modify(LSon,Pos,Val);40    else Modify(RSon,Pos,Val);41    Update(Now);return;42}43 44long long Query(int Now,int l,int r,int Type) {45    if (l>r||Node[Now].l>r||Node[Now].r<l) return INF;46    if (Node[Now].l>=l&&Node[Now].r<=r) return Type?Node[Now].MinSum:Node[Now].Min;47    return min(Query(LSon,l,r,Type),Query(RSon,l,r,Type));48}49 50long long Calc(int Val) {51    int Pos=Find(Val);52    return Tag+min(Query(1,1,Pos,0)+Val,Query(1,Pos+1,m,1));53}54 55int main() {56    freopen("revolt.in","r",stdin);57    freopen("revolt.out","w",stdout);58    scanf("%d",&n);59    for (int i=1;i<=n;i++) scanf("%d",&Line[i]),Mapping[i]=Line[i];60    Discrete();61    Build(1,m);62    int Pos=Find(Line[1]);63    Modify(1,Pos,0);64    for (int i=3;i<=n;i+=2) {65        long long Left=Calc(Line[i]);66        long long Right=Calc(Line[i-1]);67        Tag+=max(Line[i],Line[i-1]);68        Pos=Find(Line[i-1]);69        Modify(1,Pos,Left-Tag);70        Pos=Find(Line[i]);71        Modify(1,Pos,Right-Tag);72    }73    printf("%lld\n",Tag+Node[1].MinSum);74    return 0;75}