Awww Man

$\texttt{"Creeper?"}$
$\texttt{"Awww Pac-Man."}$
$\texttt{"?"}$
$\texttt{"?"}$

吃豆人(Pac-Man, パックマン)是一个简单而又有趣的游戏，游戏目标是在一个二维的地图上，吃光所有的豆子，并且过程中要避免被幽灵抓到。
贪吃蛇(Snake)也是一个简单而又有趣的游戏，游戏的目标是在一个二维的地图上，操控一个直线（蛇）不断的吃豆子，并且不要碰到墙。
一天，Vanis想到了一个更加简单的游戏，这个游戏是以上两个游戏的融合版。游戏在一个一维直线上进行，在这个一维直线上建立坐标轴，玩家操控Pac-Man来进行游戏，游戏开始时在坐标为整数 $a_0$ 的位置上，同时，在另一个整数位置 $a_1$ 上有一个分数为整数 $v_1$ 的豆子，如果玩家操控的Pac-Man吃掉了这个豆子后，将会获得分数 $v_1$ ，并且在整数 $a_2$ 位置上会出现一个分数为 $v_2$ 的豆子......实际上，游戏中总共会有n个豆子，第i个豆子出现在整数位置 $a_i$ 处，其分数为整数 $v_i$ ，通常情况下，第1颗豆子在游戏开始时便会出现，之后，当玩家吃掉第i - 1颗豆子时，会出现第i颗豆子。

在任意时刻，玩家可以向左走（位置坐标减少1个单位）或向右走（位置坐标增加1个单位），并且每移动一个单位，玩家的得分会损失C点。
另外，这个Pac-Man有一个特殊能力，在任意时刻（包括在游戏刚开始，玩家还没进行移动的时候），玩家可以选择发动这个特殊能力，发动之后，游戏会发生异变，产生如下两个效果：

1. 所有尚未出现的豆子都会立刻出现在地图上（注意：已经吃掉的豆子不会再出现），即之后可以按照任意的顺序吃完剩下的豆子。
2. 玩家仍然可以自由向左或右移动，但是每移动一个单位都会损失 $2 \times C$ 点得分。

关于吃豆子的规则，需要注意：

1. 如果Pac-Man所在的位置上出现了豆子，则这颗豆子会在出现瞬间被吃掉。
2. 如果某个位置上出现了多颗豆子，则当Pac-Man处在这个位置上时，该位置上的所有豆子都会被吃掉。

上述效果在发动后会持续到游戏结束。
游戏在所有的n颗豆子被吃掉后结束。

Vanis想要知道游戏结束时，它最大可能的得分是多少。

第一行输入两个整数n和C，之间使用一个空格符分隔，表示游戏中总共会出现的豆子数，和Pac-man每移动一个单位损失的得分。
第二行输入一个整数 $a_0$ ，表示玩家操控的Pac-Man的初始位置。
从第三行开始的第i行，输入两个整数 $a_i$ 和 $v_i$ ，两个整数之间使用一个空格符分隔，表示第i颗豆子出现的位置和吃掉后能够获得的得分，这样的输入会有n行。

数据规模：
* $0 \le n \le 10^5$ .
* $0 \le C \le 10^5$ .
* $\forall_{i \ge 0}\ \ -10^5 \le a_i \le 10^5$ .
* $\forall_{i \ge 0}\ \ 1 \le v_i \le 10^5$ .

#include <iostream> #include<map> #include<queue> #include<vector> #include<algorithm> #include<string> #include<ctime> #include<set> #include<cstring> using namespace std; typedef long long ll; map<ll, long long>r,a,d; int INF = 0x3f3f3f3f; //ll r[10050], a[10050], d[10050]; int main() { ll n, c, v=0; scanf("%lld%lld%lld", &n, &c,&r[0]); for (int i = 1; i <= n; i++) { scanf("%lld%lld", &r[i], &a[i]); v += a[i]; d[i] += d[i-1]+1ll*abs(r[i] - r[i - 1]) * c; } ll ans = v - d[n]; ll maxn = -INF, minn = INF; for (int i = n; i >= 1; i--) //判断开挂时间 { maxn = max(maxn, r[i]); minn = min(minn, r[i]); ans = max(ans, 1ll*(v - d[i - 1] - (maxn - minn) * 2 * c - min(abs(maxn - r[i - 1]), abs(minn - r[i - 1])) * c)); } printf("%lld", ans); }

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+7; int n,a[maxn],v,mx,mn; long long s[maxn],c,z,r,w; int main() { scanf("%d%lld%d",&n,&c,&a[0]); for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&v),r+=v; mx=mn=a[n]; for(int i=n-1;i>=0;i--) { s[i]=2*c*(mx-mn)+c*min(abs(mx-a[i]),abs(mn-a[i])); mx=max(mx,a[i]),mn=min(mn,a[i]); } z=1e18; for(int i=0;i<=n;i++) z=min(z,w+s[i]),w+=c*abs(a[i]-a[i+1]); printf("%lld",r-z); }

详情