洛谷p2672推销员题解

日常扯废话：

话说题解里的思路都写得真的是很奈斯啊

但是

代码看不懂确实让人头疼（可能是我太弱了）

就像题解里的第一篇题解代码简洁但是属实看不明白

趁着学姐刚给我讲了知识还热乎赶紧给泥萌说说哈

正文：

题面

思路就是贪心，使劲贪。

其实我主要是来补充一下具体的代码解释

for (int i = n; i >= ; i--)

maxsum[i] = max (maxsum[i + ],  * e[i].s + e[i].v);

这个maxsum数组存储了v由大到小， 注意是要倒着存储的。关于为什么V要从大到小因为我们有一个前缀和啊， 嗯？前缀和？对的！看 后边就懂啦！

for (int i = ; i <= n; i++)

sumv[i] = sumv[i - ] + e[i].v;

这就是我们的前缀和数组， 这个数组是存储了我们从起点走到i这个位置的时候所有的经过过的人家推销所需要的疲劳值

for (int i = ; i <= n; i++)

maxs[i] = max (maxs[i - ], e[i].s);

而这个数组则存储了当前走到的最远距离

for (int i = ; i <= n; i++)

printf ("%d\n", max (sumv[i - ] + maxsum[i], sumv[i] +  * maxs [i]));

这两行可以说是我最难理解的地方了

考虑两种情况， 第一种情况前i - 1个位置所有拜访过的疲劳值再加上最大的V， 第二种情况则为所有的v再加上最远的距离的两倍

为什么会是这两种情况， 因为最大的v可能与最远的距离不同（我的语文常年垫底）， 自己举一个例子可能会更直观。

干净一点的代码：

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

const int N = ;

int n, maxsum[N], maxs[N], sumv[N];

struct node {

    int s, v;

}e[N];

bool cmp (node x, node y) {

    return x.v > y.v;

}

int main () {

    scanf ("%d", &n);

    for (int i = ; i <= n; i++)

        scanf ("%d", &e[i].s);

    for (int i = ; i <= n; i++)

        scanf ("%d", &e[i].v);

    sort (e + , e +  + n, cmp);

    for (int i = n; i >= ; i--)

        maxsum[i] = max (maxsum[i + ],  * e[i].s + e[i].v);

    for (int i = ; i <= n; i++)

        maxs[i] = max (maxs[i - ], e[i].s);

    for (int i = ; i <= n; i++)

        sumv[i] = sumv[i - ] + e[i].v;

    for (int i = ; i <= n; i++)

        printf ("%d\n", max (sumv[i - ] + maxsum[i], sumv[i] +  * maxs [i]));

    return ;

}

谢谢收看， 祝身体健康！