洛谷P3582 [POI2015]KIN

题目描述

共有m部电影，编号为1~m，第i部电影的好看值为w[i]。在n天之中（从1~n编号）每天会放映一部电影，第i天放映的是第f[i]部。你可以选择l,r(1<=l<=r<=n)，并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。

输入输出格式

输入格式：

第一行两个整数n,m(1<=m<=n<=1000000)。第二行包含n个整数f[1],f[2],…,fn。第三行包含m个整数w[1],w[2],…,wm。

输出格式：

输出观看且仅观看过一次的电影的好看值的总和的最大值。

输入输出样例

输入样例#1：复制

9 4
2 3 1 1 4 1 2 4 1
5 3 6 6

输出样例#1：复制

说明

共有m部电影，编号为1~m，第i部电影的好看值为w[i]。

在n天之中（从1~n编号）每天会放映一部电影，第i天放映的是第f[i]部。

你可以选择l,r(1<=l<=r<=n)，并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。

大课间之前就开始想这题，买完水回来发现这题好傻……

实际上我们考虑枚举左端点，那么可不可以一边枚举左端点一边维护右端点的最优答案呢？

我们可以用线段树！

我们把每种电影开一个vector，依次插入每一场在哪天。然后对每种电影维护在当前左端点右边，且距离当前左端点最近的这种电影在哪里。这个我们一边移动一遍搞个指针就行了。然后我们的问题就变成了每一种电影都有一个出现时间段和权值，哪个点的权值和最大。那么我们就可以用线段树维护，一个区间加操作一个区间查最值操作就好了。

代码能力越来越不行了……

#include<cstdio>
#include<iostream>
#include<vector>
#define int long long
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int maxn = 1e6 + 5;
vector<int > MV[maxn];
int n, m, w[maxn], t[maxn], itr[maxn], ans;

namespace SGT {
    int mx[maxn << 2], add[maxn << 2];
    void push_up(int rt) {
        mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);
    }
    void push_down(int rt) {
        if(add[rt]) {
            add[rt << 1] += add[rt];
            add[rt << 1 | 1] += add[rt];
            mx[rt << 1] += add[rt];
            mx[rt << 1 | 1] += add[rt];
            add[rt] = 0;
        }
    }
    void Add(int l, int r, int tl, int tr, int rt, int dt) {
        if(l == tl && r == tr) 
            return mx[rt] += dt, add[rt] += dt, void();
        int mid = tl + tr >> 1;
        push_down(rt);
        if(r <= mid) Add(l, r, tl, mid, rt << 1, dt);
        else if(l > mid) Add(l, r, mid + 1, tr, rt << 1 | 1, dt);
        else Add(l, mid, tl, mid, rt << 1, dt), Add(mid + 1, r, mid + 1, tr, rt << 1 | 1, dt);
        push_up(rt);
    }
    int Qmax(int l, int r, int tl, int tr, int rt) {
        if(l == tl && r == tr) return mx[rt];
        int mid = tl + tr >> 1;
        if(r <= mid) return Qmax(l, r, tl, mid, rt << 1);
        else if(l > mid) return Qmax(l, r, mid + 1, tr, rt << 1 | 1);
        else return max(Qmax(l, mid, tl, mid, rt << 1), Qmax(mid + 1, r, mid + 1, tr, rt << 1 | 1));
    }
}

int nt, *it;
signed main() {
    scanf("%lld%lld", &n, &m);
    For(i, 1, n) scanf("%lld", &t[i]), MV[t[i]].push_back(i);
    For(i, 1, m) {
        scanf("%lld", &w[i]), MV[i].push_back(n + 1);
        if(MV[i].size() > 1)SGT::Add(MV[i][0], MV[i][1] - 1, 1, n, 1, w[i]);
    }
    ans = max(ans, SGT::Qmax(1, n, 1, n, 1));
    For(i, 1, n) {
        nt = t[i], it = &itr[nt];
        if(*it < MV[nt].size() - 1) {
            SGT::Add(MV[nt][*it], MV[nt][(*it) + 1] - 1, 1, n, 1, -w[nt]), ++(*it);
            if(*it < MV[nt].size() - 1) 
            SGT::Add(MV[nt][*it], MV[nt][(*it) + 1] - 1, 1, n, 1, w[nt]);
        }
        ans = max(ans, SGT::Qmax(i, n, 1, n, 1));
    }
    printf("%lld\n", ans);
    return 0;
}

Rockdu's Blog