Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

P1484 种树

发表于 分类于
本文字数： 2.5k 阅读时长 ≈ 2 分钟
标签：            

P1484 种树

Algorithm I 贪心

和数据备份类似。注意题目中

他至多会种 $k$ 棵树。

多维护一个 $max$ 作为最终答案。

查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
#include <queue>
using namespace std;
typedef long long LL;
typedef pair<LL, int> PLI;
const int N = 5e5 + 10;
struct Node
{
    LL v;
    int l, r;
} p[N];
int n, k;
bool vis[N];
priority_queue<PLI> q;
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &p[i].v);
        p[i].l = i - 1, p[i].r = i + 1;
        q.push(make_pair(p[i].v, i));
    }
    LL cur = 0, mx = 0;
    while (k--)
    {
        while (vis[q.top().second])
            q.pop();
        int t = q.top().second;
        q.pop();
        cur += p[t].v;
        mx = max(mx, cur);
        vis[p[t].l] = vis[p[t].r] = true;
        p[t].v = p[p[t].l].v + p[p[t].r].v - p[t].v;
        q.push(make_pair(p[t].v, t));
        p[t].l = p[p[t].l].l;
        p[t].r = p[p[t].r].r;
        p[p[t].l].r = p[p[t].r].l = t;
    }
    printf("%lld", mx);
    return 0;
}

Algorithm II wqs二分

随着选择的树的个数越多答案越大，但增长地越慢，函数为一个凸函数，可以凸优化。

查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
    #include <cstdio>
using namespace std;
const int N = 5e5 + 10;
typedef long long LL;
LL ans;
int n, m, cnt, w[N];
struct Data
{
    LL s;
    int t;
    friend Data max(Data x, Data y)
    {
        if (x.s > y.s || (x.s == y.s && x.t < y.t))
            return x;
        return y;
    }
} f[2][2];
void check(int x)
{
    f[0][0] = f[0][1] = (Data){0, 0};
    for (int i = 1; i <= n; i++)
    {
        f[i & 1][0] = max(f[i - 1 & 1][0], f[i - 1 & 1][1]);
        f[i & 1][1] = (Data){f[i - 1 & 1][0].s + w[i] - x, f[i - 1 & 1][0].t + 1};
    }
    ans = max(f[n & 1][0], f[n & 1][1]).s;
    cnt = max(f[n & 1][0], f[n & 1][1]).t;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    check(0);
    if (cnt <= m)
    {
        printf("%lld", ans);
        return 0;
    }
    int l = 0, r = 1e6, res;
    while (l <= r)
    {
        int mid = l + r >> 1;
        check(mid);
        cnt <= m ? (res = mid, r = mid - 1) : (l = mid + 1);
    }
    check(res);
    printf("%lld", ans + (LL)res * m);
    return 0;
}
相关文章