貌似这题代码可以很短欸

但是我自作孽写线段树

题目链接：P2672 推销员

不过为什么会写线段树呢，其实是因为我看了标签。

申明：本题解较适合喜欢使用数据结构的 $OIers$，并且码量较其他方法来说比较大

进入正题

可以证明每一次选择都基于上一次的选择，这个结论已经有巨佬详细地证明了，这里就不再详细说明了 或者说是我不会

这道题我选择倒过来做，大致思路：

  1. $S$ 值是从小到大排好序的（所以下文中下标更大即意味着 $S$ 值更大），可以不用管。
  2. 当每一个用户的家都需要去的时候，也就是 $X = N$ 时，答案显然是所有 $A$ 值的和加上 $Smax * 2$。又因为每一次的选择都基于上一次，也就是每一次选择都可以推导出上一次选择。
  3. 我们在求每一个状态的时候，关注的只有目前 $A$ 值的和、目前选择的点中 $S$ 的最大值 以及 当 $S$ 最大时点的下标。又因为 $A$ 值的和可以由上一个答案与目前选择的点得到，所以可以不维护。

那么，我们只需要逐步删除选中的点，并保证局部最优。这个答案一定就是所求。

以下用 $l$、$r$表示 目前选中的点中下标最小的点的下标 和 目前选中的点中下标最大的点的下标（因此 $l$，$r$ 之间有可能会有没有选中的点），$dis$ 表示 $r$ 点的 $S$ 值的两倍（即来回距离）

这样的话，对于每一个状态，我们都有两种选择来指向两个不同的上一状态，在中间取最优值：

  1. 删除 $l$ ~ $r - 1$ 中 $A$ 值最小的点 $v$，这样会尽量让答案更大，此时答案只需减去 $A_v$ 即可
  2. 删除 $r$，这会导致右端点的变化（左移），因此 $dis$ 也会发生改变，同时，答案会减去 $A_r$

最后两个方案的答案取 $max$ 并且更新状态即可。

所以我们的线段树用在哪里呢。。。终于讲到正题了

在方案 $1$ 中，我们好像要求 $l$ ~ $r - 1$ 中 $A$ 的 $min$ 值和它的下标？

线段树！

是的，线段树就用在这里 也只用在这里

所以我们的线段树就只需要维护区间最小值和区间最小值下标即可，加一个单点修改

但是当有两个点的值均为区间最小，那我们的下标应该取哪一个呢？

显然是下标更小的那一个，因为这样可以使留下来的点的 $S$ 更大， $dis$ 更大

而删除一个点之后，我们应该把其 $A$ 值变成 $INF$，这样就不会取到了。但这个操作只需要在方案 $1$ 更优的时候进行，因为在方案 $2$ 中，我们向左更新了 $r$ 的值，又所有的线段树操作都会在 $l$ ~ $r - 1$ 中进行，所以根本就不会再得到之前的 $r$ 点了

而当我们选择了方案 $1$ ，删除 $r$ 后，哪个点来“接替” $r$ 的位置呢？显然不能是 $r$ 上一个点，因为它或许没有被选中，如果选中它，则违背了题目中 “不走多余的路的前提”

所以我们还需要维护选中的点中每一个点的前一个点 绕口令

链表！

维护每个点的上一个节点即可

好的问题解决了 看起来很简单的样子

还是分几个部分讲解好了

变量声明

#define pii pair<int,int>//这里用pair来存区间min值和min值下标

const int MAXN = 1e5 + 10;
const int INF = 1e9;

int n,pre[MAXN],nxt[MAXN];//pre、nxt：链表
int seg[MAXN << 2],p[MAXN << 2];//seg：线段树区间min，p：线段树区间min下标
int ans[MAXN],l,r;//ans：x为不同数值时的答案数组

还有一个结构体

struct house {
    int a,s;
    bool operator < (const house &b) const {return a < b.a;}
} node[MAXN];

跟题目中的一样

链表

void Delete(int pos) {
    pre[nxt[pos]] = pre[pos];
    nxt[pre[pos]] = nxt[pos];
}//这是一个极其简单的删除节点函数。。。

没啥讲的

线段树

#define l ll//懒得换变量名了，就define一下
#define r rr//到时候会undef

void pushup(int root) {//更新
    if(seg[root << 1 | 1] < seg[root << 1]) {//如果右子树更优
        seg[root] = seg[root << 1 | 1];//只能存右子树的答案了
        p[root] = p[root << 1 | 1];
    } else {
        seg[root] = seg[root << 1];//否则存左子树，这样可以让下标尽量小
        p[root] = p[root << 1];
    }
}

void build(int root,int l,int r) {//简单的建树
    if(l == r) {
        seg[root] = node[l].a;
        p[root] = l;
        return;
    }
    int mid = (l + r) >> 1;
    build(root << 1,l,mid);
    build(root << 1 | 1,mid + 1,r);
    pushup(root);
}

void update(int root,int l,int r,int pos,int val) {//简单的更新
    if(l == r && l == pos) {
        seg[root] = val;
        return;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid) update(root << 1,l,mid,pos,val);
    else update(root << 1 | 1,mid + 1,r,pos,val);
    pushup(root);
}

pii getmin(pii &a,pii b) {//类似于min函数，用来找两个pii中最小值较小的那个（即当前的返回值）
    if(b.first < a.first) swap(a,b);
}

pii query(int root,int l,int r,int L,int R) {
    if(L <= l && r <= R) return make_pair(seg[root],p[root]);
    int mid = (l + r) >> 1;
    pii res = make_pair(INF,INF);
    if(L <= mid) getmin(res,query(root << 1,l,mid,L,R));//这里用到了getmin，可以自己研究一下
    if(R > mid) getmin(res,query(root << 1 | 1,mid + 1,r,L,R));
    return res;
}

#undef l
#undef r//说了会undef

主函数

int main () {
    ios::sync_with_stdio(0);//优化
    cin >> n;
    for(register int i = 1;i <= n; ++i)
        cin >> node[i].s;
    for(register int i = 1;i <= n; ++i) {
        cin >> node[i].a;
        pre[i] = i - 1;
        nxt[i] = i + 1;//链表初始化
        ans[n] += node[i].a;//最终答案
    }
    build(1,1,n);//建树
    l = 1,r = n;//左右端点（实际只有 r 有用）
    ans[n] += node[r].s * 2;//答案要加上dis
    for(register int i = n - 1;i >= 1; --i) {//倒推答案
        pii tmp = query(1,1,n,l,r - 1);//方案1 中用线段树
        int ans1 = ans[i + 1] - tmp.first;//方案1
        int ans2 = ans[i + 1] - node[r].a - node[r].s * 2 + node[pre[r]].s * 2;//方案2，也就是减去 r 的s*2和a，再加上新r的s*2
        if(ans1 < ans2) {//如果方案1更优
            int ss = r;
            r = pre[r]; Delete(ss);//删除右端点，更新右端点
            ans[i] = ans2;//更新答案
        } else {
            Delete(tmp.second);//删除当前下标
            update(1,1,n,tmp.second,INF);//更新，把当前A变成INF
            ans[i] = ans1; //更新答案
        }
    }
    for(register int i = 1;i <= n; ++i)
        cout << ans[i] << endl;//输出
    return 0;//华丽丽地结束
}

最后附上完整代码

//Code By CXY
#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>//这里用pair来存区间min值和min值下标

const int MAXN = 1e5 + 10;
const int INF = 1e9;

struct house {
    int a,s;
    bool operator < (const house &b) const {return a < b.a;}
} node[MAXN];

int n,pre[MAXN],nxt[MAXN];//pre、nxt：链表
int seg[MAXN << 2],p[MAXN << 2];//seg：线段树区间min，p：线段树区间min下标
int ans[MAXN],l,r;//ans：x为不同数值时的答案数组

#define l ll//懒得换变量名了，就define一下
#define r rr//到时候会undef

void pushup(int root) {//更新
    if(seg[root << 1 | 1] < seg[root << 1]) {//如果右子树更优
        seg[root] = seg[root << 1 | 1];//只能存右子树的答案了
        p[root] = p[root << 1 | 1];
    } else {
        seg[root] = seg[root << 1];//否则存左子树，这样可以让下标尽量小
        p[root] = p[root << 1];
    }
}

void build(int root,int l,int r) {//简单的建树
    if(l == r) {
        seg[root] = node[l].a;
        p[root] = l;
        return;
    }
    int mid = (l + r) >> 1;
    build(root << 1,l,mid);
    build(root << 1 | 1,mid + 1,r);
    pushup(root);
}

void update(int root,int l,int r,int pos,int val) {//简单的更新
    if(l == r && l == pos) {
        seg[root] = val;
        return;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid) update(root << 1,l,mid,pos,val);
    else update(root << 1 | 1,mid + 1,r,pos,val);
    pushup(root);
}

pii getmin(pii &a,pii b) {//类似于min函数，用来找两个pii中最小值较小的那个（即当前的返回值）
    if(b.first < a.first) swap(a,b);
}

pii query(int root,int l,int r,int L,int R) {
    if(L <= l && r <= R) return make_pair(seg[root],p[root]);
    int mid = (l + r) >> 1;
    pii res = make_pair(INF,INF);
    if(L <= mid) getmin(res,query(root << 1,l,mid,L,R));//这里用到了getmin，可以自己研究一下
    if(R > mid) getmin(res,query(root << 1 | 1,mid + 1,r,L,R));
    return res;
}

#undef l
#undef r//说了会undef

void Delete(int pos) {
    pre[nxt[pos]] = pre[pos];
    nxt[pre[pos]] = nxt[pos];
}//这是一个极其简单的删除节点函数。。。

int main () {
    ios::sync_with_stdio(0);//优化
    cin >> n;
    for(register int i = 1;i <= n; ++i)
        cin >> node[i].s;
    for(register int i = 1;i <= n; ++i) {
        cin >> node[i].a;
        pre[i] = i - 1;
        nxt[i] = i + 1;//链表初始化
        ans[n] += node[i].a;//最终答案
    }
    build(1,1,n);//建树
    l = 1,r = n;//左右端点（实际只有 r 有用）
    ans[n] += node[r].s * 2;//答案要加上dis
    for(register int i = n - 1;i >= 1; --i) {//倒推答案
        pii tmp = query(1,1,n,l,r - 1);//方案1 中用线段树
        int ans1 = ans[i + 1] - tmp.first;//方案1
        int ans2 = ans[i + 1] - node[r].a - node[r].s * 2 + node[pre[r]].s * 2;//方案2，也就是减去 r 的s*2和a，再加上新r的s*2
        if(ans1 < ans2) {//如果方案1更优
            int ss = r;
            r = pre[r]; Delete(ss);//删除右端点，更新右端点
            ans[i] = ans2;//更新答案
        } else {
            Delete(tmp.second);//删除当前下标
            update(1,1,n,tmp.second,INF);//更新，把当前A变成INF
            ans[i] = ans1; //更新答案
        }
    }
    for(register int i = 1;i <= n; ++i)
        cout << ans[i] << endl;//输出
    return 0;//华丽丽地结束
}

其实用线段树也蛮有趣的，大家可以试试鸭

初二的 $OIer$ ，请多关照

标签: 线段树, dp

添加新评论