AtCoder AGC030B Tree Burning

题目链接

https://atcoder.jp/contests/agc030/tasks/agc030_b

题解

细节好题。。

首先假设第一步往右走，那么可以发现当拐弯的次数一定时路径是唯一的

于是可以枚举这个值

然后很烦的是枚举之后要分奇偶讨论。。

最后再翻过来做一遍处理第一步往左走就行了

时间复杂度\(O(n)\)

代码

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define llong long long

using namespace std;

void read(int &x)

{

    int f=1;x=0;char s=getchar();

    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}

    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}

    x*=f;

}

const int N = 2e5;

llong a[N+3];

llong s[N+3];

int n; llong m,ans;

void solve()

{

	s[0] = 0ll; for(int i=1; i<=n; i++) s[i] = s[i-1]+a[i];

	for(int i=1; i<=n; i++)

	{

		llong tmp;

		if(i&1)

		{

			int x = (i-1)>>1;

			tmp = (m*x-(s[n]-s[n-x]))*2+a[n-x]+(s[n-x-1]-s[n-x-x-1])*2;

		}

		else

		{

			int x = i>>1;

			tmp = (m*(x-1)-(s[n]-s[n-x+1]))*2+(m-a[n-x+1])+(s[n-x]-s[n-x-x])*2;

		}

		ans = max(ans,tmp);

	}

}

int main()

{

	scanf("%lld%d",&m,&n);

	for(int i=1; i<=n; i++) scanf("%lld",&a[i]);

	solve();

	for(int i=1; i<=n; i++) a[i] = m-a[i];

	reverse(a+1,a+n+1);

	solve();

	printf("%lld\n",ans);

	return 0;

}

巴特西

AtCoder AGC030B Tree Burning

题目链接

题解

代码

最新文章

热门文章