B. Light It Up （前缀和、模拟）

╰半橙微兮° 2021-07-16 11:25 341阅读 0赞

[题目][Link 1]

预先做好一个所有偶数与前一个数差值和3以后奇数a\[i\]和前一个数差值的前缀和b\[i\]（代表插入数后的情况），然后遍历插入到所有数后面的情况，假设插入到第i个数那么前i个数的贡献用a\[i-1\]表示，插入中间的贡献用lst\[i\]-lst\[i-1\]-1表示，后面的贡献用b\[n+2\]-b\[i\]表示，算出最大贡献即可。

Code:

#include<iostream>
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    ll a[Max], b[Max], lst[Max];
    
    int main()
    { 
    	int n, m;cin >> n >> m;
    	ll sum = 0;
    	lst[1] = 0;lst[n + 2] = m;
    	for (int i = 2;i <= n + 1;i++)
    	{ 
    		cin >> lst[i];
    		a[i] = a[i - 1];
    		b[i] = b[i - 1];
    		if (i % 2 == 1)b[i] += lst[i] - lst[i - 1];
    		else a[i] += lst[i] - lst[i - 1];
    	}
    	a[n + 2] = a[n + 1];
    	b[n + 2] = b[n + 1];
    	if ((n + 2) % 2 == 1)b[n + 2] += lst[n + 2] - lst[n + 1];
    	else a[n + 2] += lst[n + 2] - lst[n + 1];
    	ll ans = a[n + 2];
    	for (int i = 2;i <= n + 2;i++)
    	{ 
    		if (i % 2 == 0) ans = max(ans, lst[i] - lst[i - 1] - 1 + b[n + 2] - b[i] + a[i - 2]);
    		else ans = max(ans, lst[i] - lst[i - 1] - 1 + a[i - 1] + b[n + 2] - b[i]);
    	}
    	cout << ans << endl;
    }

[Link 1]: https://codeforc.es/problemset/problem/1000/B

发表评论取消回复

表情：

评论列表（有 0 条评论，341人围观）

还没有评论，来说两句吧...

相关阅读

相关 Sum It Up

Sum It Up Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Ot

谁借莪１个温暖的怀抱￠/ 2024年02月18日 23:13/ 0 赞/ 54 阅读

相关 Light 1249-Chocolate Thief【模拟】

1249 - Chocolate Thief <table> <tbody> <tr> <td title="normal judge" style="co

比眉伴天荒/ 2022年08月21日 14:53/ 0 赞/ 85 阅读

相关 ACM 模拟 Just Finish it up

滴，集训第八天打卡。今天还是第八章训练，看着书上的分析做了一下午，感觉人生得到了升华... UVA 11093 Just Finish it up ![20

╰+攻爆jí腚メ/ 2022年06月12日 14:56/ 0 赞/ 165 阅读

相关 Sum It Up

Sum It Up Problem Description Given a specified total t and a list of n integers, f

阳光穿透心脏的1/2处/ 2022年05月16日 11:21/ 0 赞/ 128 阅读

相关 DFS-HDU 1258-Sum It Up

DFS-HDU 1258-Sum It Up -------------------- 题目链接：[Sum It Up][] 思路：题目

Love The Way You Lie/ 2022年05月15日 01:19/ 0 赞/ 347 阅读

相关【POJ - 3087】Shuffle'm Up(模拟)

[Shuffle'm Up][Shuffle_m Up] 直接写中文了 Descriptions: 给定两个长度为len的字符串s1和s2，接着给出一个长度为len

我会带着你远行/ 2021年11月26日 17:30/ 0 赞/ 193 阅读

相关 Sum It Up ( dfs ➕ 去重)

Problem Description Given a specified total t and a list of n integers, find all distin

港控/mmm°/ 2021年11月10日 12:46/ 0 赞/ 203 阅读

相关 HDU-1258 Sum It Up （DFS）

题意：输入一个m，和n个数，输出所有数据组合相加和为m的组合，输出的数列不重复； emmmm....一开始是想dfs全找出来存起来然后去重，然后发现自己数据结构也很菜，实现不

约定不等于承诺〃/ 2021年10月19日 11:22/ 0 赞/ 204 阅读

相关 1498C - Planar Reflections （暴力+前缀和+模拟）

[题目][Link 1] 思路：模拟一下过程，有n个平面，那么在一次飞跃中位于第1个平面的粒子向右飞会在后面每个平面都产生一个粒子，那第一个平面有m个粒子后面每个平面2–

小灰灰/ 2021年07月16日 18:38/ 0 赞/ 362 阅读

相关 B. Light It Up （前缀和、模拟）

[题目][Link 1] 预先做好一个所有偶数与前一个数差值和3以后奇数a\[i\]和前一个数差值的前缀和b\[i\]（代表插入数后的情况），然后遍历插入到所有数后面的情

╰半橙微兮°/ 2021年07月16日 11:25/ 0 赞/ 342 阅读