题目
Static Sushi
一个圆桌上摆着n个食物，吃掉每个食物得到一定能量，沿着圆桌任意顺时针逆时针走，每走一米消耗1点能量，求能够得到的最大能量。
思路
一共4种走法：
- 顺时针走到某位置离开；
- 逆时针走到某位置离开；
- 顺时针走，而后走回原点，在逆时针走到某位置，离开；
- 逆时针走，而后走回原点，在顺时针走到某位置，离开；
预处理如下代码的四个数组，计算这4种情况即可。
总结
代码
点击查看代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using LL = long long;
void solv()
{
int n;
LL c, t;
cin >> n >> c;
vector<LL> x(n + 1), v(n + 1);
vector<LL> sum11(n + 1, 0), sum21(n + 1, 0), sum12(n + 1, 0), sum22(n + 1, 0);
for (int i = 0; i < n; i ++)
cin >> x[i] >> v[i];
LL sumv = 0;
for (int i = 0; i < n; i ++)
{
sumv += v[i];
t = sumv - x[i];
// 顺时针走到某位置而后离开，考虑前i个物品，能够得到的累计最大收益
sum11[i] = i > 0 ? max(sum11[i - 1], t) : max(0ll, t);
// 顺时针走到某位置而后走回起点，考虑前i个物品，能够得到的累计最大收益
sum12[i] = i > 0 ? max(sum12[i - 1], t - x[i]) : max(0ll, t - x[i]);
}
sumv = 0;
for (int i = n - 1; i >= 0; i --)
{
sumv += v[i];
t = sumv - (c - x[i]);
// 逆时针走到某位置而后离开，考虑i~n-1个物品，能够得到的累计最大收益
sum21[i] = i < n - 1 ? max(sum21[i + 1], t) : max(0ll, t);
// 逆时针走到某位置而后走回起点，考虑i~n-1个物品，能够得到的累计最大收益
sum22[i] = i < n - 1 ? max(sum22[i + 1], t - (c - x[i])) : max(0ll, t - (c - x[i]));
}
LL ans = max(sum11[n-1], sum21[0]); // 单纯顺时针走 or 单纯逆时针走 能够得到的最大收益
for (int i = 0; i < n; i ++)
{
// 顺时针走，而后走回原点，在逆时针走到某位置，离开
ans = max(ans, sum12[i] + sum21[i + 1]);
// 逆时针走，而后走回原点，在顺时针走到某位置，离开
ans = max(ans, sum11[i] + sum22[i + 1]);
}
cout << ans << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
solv();
return 0;
}