题解：P2672 [NOIP2015 普及组] 推销员

· · 题解

题目大概是要求这个东西：给定 n 个数对 (x_i,c_i)，让你求对于每个 k，从中选出 k 个数对（这里编号为 A_1\sim A_k），使得：

(\max_{1\leq i \leq k}x_{A_i}\times 2) + \sum_{i=1}^k c_{A_i}

最大。

Sub1

直接爆搜即可，复杂度 O(N\times 2^N)。

Sub2

不难想到定义一个 dp，令 dp_{i,j,k} 表示前 i 户人家推销了 j 户上一户推销的人家是第 k 户的最大值，转移是简单的，直接枚举上一次是从哪一户转移过来的即可。

时间复杂度 O(N^4)，空间复杂度 O(N^3)。

Sub3

从网上看到个比较奇怪的 O(N^2) 做法（奇怪是我觉得这明明可以直接弄成正解的），分享一下。大概思路是去贪心地在上一次选择的基础上再选择一个最优的住户，前提是先预处理出 k=1 时的答案。

具体可以自己去那篇 blog 去看。

Sub4

正解，Sub3 的奇怪做法提醒了我们「贪心地增加一个最优的用户」。

做这个题之前应该会想到一个乱搞结论：直接选 k 个 c_i 最大的住户算就可以了。

但是动动脑子就会发现这肯定是错的，比如我可以构造一组数据让前 k 大的 c_i 的 x_i 都很小，最后再放一个 x_i=\infty。

但是我们灵机一动，从上面那段话以及最开始那个式子可以注意到，答案只与我们选的最大的一个 x_i 有关系，剩下的 k-1 个 x_i 爱怎么选怎么选。

所以我们想到，既然 k-1 个 x_i 爱怎么选怎么选，那么我们不妨直接选前 k-1 个 c_i 最大的，再补充一个数 p，使得：

x_p \geq \max_{1\leq i < k} x_{A_i}

且

2\times (x_p-\max_{1\leq i < k} x_{A_i})+c_p

最大。

所以我们可以按 c_i 从大到小排序，用个前后缀优化就可以了。

但是我用我两百万年前写的 code 交上去发现被 hack 了，原因是我们最开始可能乱猜的结论有那么一点道理（说人话就是上面的做法会漏掉一些情况），为了完善一些可能会错误的情况，我们需要和我们乱猜的结论取 \max，这样的话就一定是对的了，因为两种情况已经覆盖了所有可能的解，而我们瞎猜的结论弥补了上述结论的漏洞，即补充的那个 p 在一定情况下不如再取第 k 大的数更优，读者自行证明，这里不再做解释了。

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(0), cin.tie(nullptr), cout.tie(nullptr);
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define pre(i, j, k) for(int i = j; i >= k; --i)
#define pb push_back
#define PII pair<int, int>
#define fi first
#define se second
#define int long long
#define inf LONG_LONG_MAX
#define repx(i, x) for(int i = head[x]; i; i = nxt[i])

using namespace std;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;

int n, m, pre[N], mx[N], suf[N];

struct node {
    int x, c;
    #define x(p) t[p].x
    #define c(p) t[p].c
    bool operator < (const node &a) const {return c > a.c;
    }
} t[N];

signed main() {
    FASTIO

    cin >> n;
    rep(i, 1, n) cin >> x(i);
    rep(i, 1, n) cin >> c(i);

    sort(t + 1, t + 1 + n);
    rep(i, 1, n) pre[i] = pre[i - 1] + c(i), mx[i] = max(mx[i - 1], x(i));//情况1
    pre(i, n, 1) suf[i] = max(suf[i + 1], x(i) * 2 + c(i));//情况2
    rep(i, 1, n) cout << max(pre[i] + 2 * mx[i], pre[i - 1] + suf[i]) << '\n';
    return 0; 
}