AtCoder 096 D 题解报告

「爱情、让人受尽委屈。」 2022-05-26 10:17 131阅读 0赞

# 一、题目 #

[https://arc096.contest.atcoder.jp/tasks/arc096\_b][https_arc096.contest.atcoder.jp_tasks_arc096_b]

# 二、分析 #

已知一个圆形柜台周长为c；你在x=0的位置，圆形柜台上存在n个点，每个点x\[i\]上有能量为v\[i\]的食物，并且你每走一步消耗1点能量（这里自身能量可以为负），求你在这环形道路上走时，某一时刻自身拥有的最大能量是多少。

因为是一个环，我们可以正向走也可以反向走，同时还可以先正向走到某个点 i 再回到x=0处然后反向走到某个大于 i的点，也可以先反向走到某个点 i 再回到x=0处然后正向走到某个小于 i 的点，在这4种情况中获得的最大能量就是答案了。

前面2种情况直接一路扫过去就行，后面2种情况需要事先预处理出2个数组，一个是正向与反向走到 i 点能获得的最大能量 dp\[0\]\[i\]和dp\[1\]\[i\]，另一个是正向和反向走到 i 点然后再回到x=0处所获得的能量g\[0\]\[i\]和g\[1\]\[i\]。

那么后面2种情况对于走到某个点能获得的最大能量就是max（g\[0\]\[i\] + dp\[1\]\[i + 1\] , g\[1\]\[i\] + dp\[0\]\[i - 1\] )。

# 三、代码 #

#include<iostream>
    using namespace std;
    
    #define ll long long
    
    const int maxn = 1e5 + 500;
    ll dp[2][maxn]; //dp[0][i]表示正向走到i点获得的最大能量，dp[1][i]为反向...
    ll g[2][maxn];  //g[0][i]表示正向走到i点回到x=0位置所拥有的能量，g[1][i]反之...
    ll x[maxn], v[maxn];
    ll n, c, sum;
    
    int main()
    {
     cin >> n >> c;
     for (int i = 1; i <= n; i++)
     { 
     cin >> x[i] >> v[i];
     }
    
     //正向遍历
     for (int i = 1; i <= n; i++)
     { 
     sum += v[i];
     dp[0][i] = max(dp[0][i - 1], sum - x[i]);
     g[0][i] = sum - 2 * x[i];
     }
    
     sum = 0;
     //反向遍历
     for (int i = n; i >= 1; i--)
     { 
     sum += v[i];
     dp[1][i] = max(dp[1][i + 1], sum - (c - x[i]));
     g[1][i] = sum - 2 * (c - x[i]);
     }
    
     ll ans = max(dp[0][n], dp[1][1]);
    
     for (int i = 1; i <= n; i++)
     { 
     //顺着走到i，再逆着走到i+1
     ans = max(ans, g[0][i] + dp[1][i + 1]);
     //逆着走到i，再顺着走到i-1
     ans = max(ans, g[1][i] + dp[0][i - 1]);
     }
    
     cout << ans;
    
     return 0;
    }

> TopCoder & Codeforces & AtCoder交流QQ群：648202993  
> 更多内容请关注微信公众号  
> ![wechat\_public.jpg][wechat_public.jpg]

[https_arc096.contest.atcoder.jp_tasks_arc096_b]: https://arc096.contest.atcoder.jp/tasks/arc096_b
[wechat_public.jpg]: /images/20220526/b39fdf66b7d94c329b35778b50adc258.png