设为首页 加入收藏

TOP

题解 DTOJ 1865 【最佳挤奶方案 (optmilk)】
2019-01-06 12:08:37 】 浏览:18
Tags:题解 DTOJ 1865 最佳 挤奶 方案 optmilk

欢迎访问 My Luogu Space


【题目描述】

Farmer John最近购买了 \(N(1 <= N <= 40000)\) 台挤奶机,编号为 \(1 ... N\),并排成一行。第 \(i\) 台挤奶机每天能够挤 \(M(i)\) 单位的牛奶 \((1 < =M(i) <=100,000)\) 。由于机器间距离太近,使得两台相邻的机器不能在同一天使用。Farmer John可以自由选择不同的机器集合在不同的日子进行挤奶。在 \(D(1 < = D < = 50,000)\) 天中,每天Farmer John对某一台挤奶机进行维护,改变该挤奶机的当天产量。

Farmer John希望设计一个挤奶方案,使得挤奶机能够在 \(D\) 天后获取最多的牛奶。

【 输入输出格式】

输入格式:

\(1\) 行:两个整数 \(N\)\(D\)

\(2..N+1\) 行:每台挤奶机的 \(M(i)\)

\(N+2..N+D+1\) 行:两个整数 \(i\)\(m\),表示每天对机器 \(i\) 进行维护,机器i的产量为 \(m\)

输出格式:

一个数组表示最大产量

【输入输出样例】

输入样例:

5 3
1
2
3
4
5
5 2
2 7
1 10

输出样例:

32

【提示】

【样例说明】
\(1\) 天,最优方案为 \(2+4=6\) ( 方案 \(1+3+2\)一样)
\(2\) 天,最优方案为 \(7+4=11\)
\(3\) 天,最优方案为 \(10+3+2=15\)


【标签】

线段树,单点修改,区间DP。


【分析】

通过线段树来进行区间DP,维护最大点集。

基本想法:

化简题目:将 \(n\) 个点排成一排,每一个点都有一个点权,从中选出相互不能临近的最大点集。

改进:

由于需要维护区间信息,考虑通过线段树来进行区间DP。

每个线段树的节点内都有一个\(F\)数组:

  1. \(F[1][0]\) 表示区间左端点取,右端点不取的最大点集的和。
  2. \(F[0][1]\) 表示区间左端点不取,右端点取的最大点集的和。
  3. \(F[1][1]\) 表示区间左端点取,右端点也取的最大点集的和。
  4. \(F[0][0]\) 表示区间左端点、右端点都不取的最大点集的和。

因为两个相邻的点不能同时取,所以更新最大值的时候要进行分类讨论,举例当前树节点可以由:

  1. 子节点的 \(F[1][0]\) \(+\) 子节点的 \(F[1][0]\)
  2. 子节点的 \(F[1][0]\) \(+\) 子节点的 \(F[0][0]\)
  3. 子节点的 \(F[1][1]\) \(+\) 子节点的 \(F[0][0]\)

三种情况取最大值得来,其他情况同理,在更新时讨论即可。

在建树时叶子节点的值为\(F[1][1] = S[l]\)

每组数据读入后进行线段树单点修改,\(Ans\) 增加线段树根节点的所有情况中的最大值即可。


【代码】

[C++]

#include <bits/stdc++.h>
#define wld(a) while(a(isdigit(c=getchar())))
#define xpp x=(x<<1)+(x<<3)+(c^48)
#define LL long long
#define R k<<1|1
#define L k<<1
using namespace std;
const int MAXN = 40000+5;
struct T{LL F[2][2];int l, r;}T[MAXN*4];

int S[MAXN], n, d, p, v;
long long Ans;

inline int Rd(){char c;wld(!);int x=c^48;wld()xpp;return x;}
inline void Update(int &k){  //更新数据
    T[k].F[1][0] = max(max(T[L].F[1][0]+T[R].F[1][0], T[L].F[1][1]+T[R].F[0][0]), T[L].F[1][0]+T[R].F[0][0]);
    T[k].F[0][1] = max(max(T[L].F[0][1]+T[R].F[0][1], T[L].F[0][0]+T[R].F[1][1]), T[L].F[0][0]+T[R].F[0][1]);
    T[k].F[0][0] = max(max(T[L].F[0][1]+T[R].F[0][0], T[L].F[0][0]+T[R].F[1][0]), T[L].F[0][0]+T[R].F[0][0]);
    T[k].F[1][1] = max(max(T[L].F[1][0]+T[R].F[1][1], T[L].F[1][1]+T[R].F[0][1]), T[L].F[1][0]+T[R].F[0][1]);
}
void Build(int k, int l, int r){  //建树
    T[k].l = l, T[k].r = r;
    if(l==r){T[k].F[1][1] = S[l];return;}
    int mid = (l+r)>>1;
    Build(L, l, mid);
    Build(R, mid+1, r);
    Update(k);
}
void Revise(int k){  //单点修改
    if(T[k].l==T[k].r){T[k].F[1][1]=v;return;}
    int Tmid = (T[k].l+T[k].r)>>1;
    if(p<=Tmid) Revise(L);
    else Revise(R);
    Update(k);
}
int main(){
    n=Rd(), d=Rd();
    for(int i=1; i<=n; i++) S[i]=Rd();
    Build(1, 1, n);
    while(d--){
        p=Rd(), v=Rd();
        Revise(1);
        Ans += max(max(T[1].F[1][1], T[1].F[0][0]), max(T[1].F[1][0], T[1].F[0][1]));
    }
    printf("%lld", Ans);
    return 0;
}

【补充】

分类讨论时要细心一点,要记得是先修改再统计。


Over


编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇BZOJ4337: BJOI2015 树的同构(has.. 下一篇cf121C. Lucky Permutation(康托..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(214) }