• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

Codeforces 1016C - Vasya And The Mushrooms(二维前后缀和 + 思维)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

题目大意:

给出一个 2 * n 的地图,输入两行,表示每分钟蘑菇的增长速率,你可以上下左右四个方向移动,但是必须遍历完全地图,因此不能走死路,每分钟只能走一步,询问当走完全地图时,你可以获得的蘑菇最大数是多少,初始时间为0,即第一步之前你没有蘑菇。

解题思路:


S为起点,E为终点的位置。根据题意得到要想遍历全图E的落点只可能是这几个方向。

当E的落点在第二行时,只可能是奇数列,他的左边是曲折的,而右边是一个顺时针行走的方形,所以我们要预处理从S点到(2, 1)的顺时针方向前缀和。

当E的落点在第一行时,只可能是偶数列,他的左边是曲折的,而右边是一个逆时针行走的方形,所以我们要预处理从(2, 1)到S点的逆时针方向前缀和。

还要处理每列(第一行和第二行相加)的前缀和,后面会用到。

之后计算该点左边的最大值和右边的最大值,到时候只需要遍历 1 -> n,每次max(ans, ls[i] + rs[i])即可。

sum数组的作用是:顺时针逆时针只是算的按初始顺序1 2 3 …的前缀和,其实实际上可能更大(因为左边走完了要加上额外的步数),所以要加上一个差,差用sum[i]去补。

Code:

#pragma GCC optimize(2)
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 6e5 + 50;
ll h1[N], h2[N];//第一行第二行的值
ll ls[N], rs[N];//点左边的值和右边的值
ll ss[N], nn[N];//顺时针和逆时针前缀和
ll sum[N];//每列的后缀和
int n;
void solve()
{
	for (int i = n; i >= 1; i --)//处理每列前缀和
		sum[i] = sum[i + 1] + h1[i] + h2[i];
	for (int i = 1; i <= n; i ++)//处理顺时针和逆时针(逆时针从第二行先开始)
	{
		ss[i] = ss[i - 1] + h1[i] * (i - 1);
		nn[i] = nn[i - 1] + h2[i] * (i - 1);
	}
	for (int i = n; i >= 1; i --)//处理顺时针和逆时针(第一行)
	{
		ss[2 * n - i + 1] = ss[2 * n - i] + h2[i] * (2 * n - i);
		nn[2 * n - i + 1] = nn[2 * n - i] + h1[i] * (2 * n - i);
	}
	for (int i = 1; i <= n; i ++)
	{
		if (i & 1)
		{
			rs[i] = ss[2 * n - i + 1] - ss[i - 1] + sum[i] * (i - 1);
			ls[i] = ls[i - 1] + h1[i - 1] * (2 * i - 3) + h2[i - 1] * (2 * i - 4);
		}
		else
		{
			rs[i] = nn[2 * n - i + 1] - nn[i - 1] + sum[i] * (i - 1);
			ls[i] = ls[i - 1] + h1[i - 1] * (2 * i - 4) + h2[i - 1] * (2 * i - 3);
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i ++)
		cin >> h1[i];
	for (int i = 1; i <= n; i ++)
		cin >> h2[i];
	solve();
	ll ans = -1;
	for (int i = 1; i <= n; i ++)
		ans = max(ans, ls[i] + rs[i]);
	cout << ans << endl;
	return 0;
}

鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C++中的inline用法发布时间:2022-07-14
下一篇:
理解c语言中的指针发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap