題目鏈接

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

題解

細(xì)節(jié)好題。。
首先假設(shè)第一步往右走，那么可以發(fā)現(xiàn)當(dāng)拐彎的次數(shù)一定時(shí)路徑是唯一的
于是可以枚舉這個(gè)值
然后很煩的是枚舉之后要分奇偶討論。。
最后再翻過(guò)來(lái)做一遍處理第一步往左走就行了
時(shí)間復(fù)雜度\(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; }

總結(jié)

以上是生活随笔為你收集整理的AtCoder AGC030B Tree Burning的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。