洛谷 P1220 关路灯

// ✗ P1220 的第一版：**题面替你写好的那个错觉**。
//
// 题面原话：「开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率，
// 然后**选择先关掉功率大的一边**，再回过头来关掉另一边的路灯，**而事实并非如此**，
// 因为在关的过程中适当地调头有可能会更省一些。」
//
// ⇒ 这一版就是把那句话写成代码：比一比两边的总功率，先一路关掉大的那边，再回头关另一边。
// ★ 它给出的是**一个合法方案** ⇒ 答案**恒 ≥ 正解**。页面上量了它到底差多少。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int n, c;
    if (scanf("%d %d", &n, &c) != 2) return 0;
    vector<ll> pos(n + 2, 0), w(n + 2, 0);
    for (int i = 1; i <= n; i++) if (scanf("%lld %lld", &pos[i], &w[i]) != 2) return 0;

    ll leftW = 0, rightW = 0;
    for (int i = 1; i < c; i++) leftW += w[i];
    for (int i = c + 1; i <= n; i++) rightW += w[i];

    // 先关功率大的那一边，再回头关另一边
    vector<int> order;
    if (leftW >= rightW) { for (int i = c - 1; i >= 1; i--) order.push_back(i);
                           for (int i = c + 1; i <= n; i++) order.push_back(i); }
    else                 { for (int i = c + 1; i <= n; i++) order.push_back(i);
                           for (int i = c - 1; i >= 1; i--) order.push_back(i); }

    ll cost = 0, here = pos[c];
    vector<char> off(n + 2, 0);
    off[c] = 1;
    for (int idx : order) {
        ll rest = 0;
        for (int i = 1; i <= n; i++) if (!off[i]) rest += w[i];
        cost += llabs(here - pos[idx]) * rest;
        here = pos[idx];
        off[idx] = 1;
    }
    printf("%lld\n", cost);
    return 0;
}

// P1220 关路灯 —— ★ 这一版就能 AC。
//
// ★★ 关键的一步：**状态在「区间」之外还要多记一维 —— 人现在站在左端还是右端。**
//
//   f[l][r][0/1] = 已经把第 l..r 盏灯全关掉、此刻人站在 **l（0）／ r（1）**，
//                  到目前为止**已经消耗**的电量最小值。
//
//   为什么必须多这一维：下一步要么去左边、要么去右边，而**走多远取决于人在哪头** ——
//   只记区间的话，这个信息就丢了（见 p1220NoSide.cpp）。
//
// ★★ 第二个要想清楚的：**走路的时候，还亮着的灯一直在耗电**。
//   所以每走一段距离 d，代价是 `d × (区间外还亮着的灯的总功率)` ——
//   注意是**区间外**（已关的那些不再耗电），用前缀和 O(1) 算出来。
//
// ⚠ 题面还替你把一个错觉写出来了：「他以为先算左右总功率、先关功率大的一边，
//   **而事实并非如此**，因为在关的过程中适当地调头有可能会更省」。
//   ⇒ 那个贪心值多少，页面第 ① 步量了。
//
// 规模：`n ≤ 50` ⇒ 状态 `50 × 50 × 2`，转移 O(1)，几千次就跑完。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, c;
    if (scanf("%d %d", &n, &c) != 2) return 0;
    vector<long long> pos(n + 2, 0), w(n + 2, 0), s(n + 2, 0);
    for (int i = 1; i <= n; i++) {
        if (scanf("%lld %lld", &pos[i], &w[i]) != 2) return 0;
        s[i] = s[i - 1] + w[i];
    }
    long long total = s[n];
    auto outside = [&](int l, int r) { return total - (s[r] - s[l - 1]); };

    const long long INF = LLONG_MAX / 4;
    vector<vector<array<long long, 2>>> f(n + 2, vector<array<long long, 2>>(n + 2, { INF, INF }));
    f[c][c][0] = f[c][c][1] = 0;

    for (int len = 2; len <= n; len++)
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            // 站在 l：上一步刚关掉的是 [l+1, r]，人在 l+1 或 r
            f[l][r][0] = min(f[l + 1][r][0] + (pos[l + 1] - pos[l]) * outside(l + 1, r),
                             f[l + 1][r][1] + (pos[r] - pos[l]) * outside(l + 1, r));
            // 站在 r：上一步刚关掉的是 [l, r-1]，人在 l 或 r-1
            f[l][r][1] = min(f[l][r - 1][1] + (pos[r] - pos[r - 1]) * outside(l, r - 1),
                             f[l][r - 1][0] + (pos[r] - pos[l]) * outside(l, r - 1));
        }
    printf("%lld\n", min(f[1][n][0], f[1][n][1]));
    return 0;
}

// ✗ P1220 的第二版：**只记区间，不记人站在哪一端**。
//
// 状态写成 f[l][r]，转移时默认「人就在**刚刚关掉的那一头**」：
//     f[l][r] = min( f[l+1][r] + (pos[l+1] − pos[l]) × 外面的功率,
//                    f[l][r−1] + (pos[r] − pos[r−1]) × 外面的功率 )
//
// ⚠ 它丢掉的正是这道题的全部门道：**人可能在另一头**，得先走过来。
//   于是它算出来的电费比真实的**少**（它偷偷把人瞬移到了近的那一端）
//   ⇒ 答案**恒 ≤ 正解**，是一个**做不到的**方案。
//
// ★ 这和「贪心那一版恒 ≥ 正解」正好是一对：
//   一个给出合法但不最优的方案（偏大），一个算的是根本走不出来的方案（偏小）。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int n, c;
    if (scanf("%d %d", &n, &c) != 2) return 0;
    vector<ll> pos(n + 2, 0), w(n + 2, 0), s(n + 2, 0);
    for (int i = 1; i <= n; i++) {
        if (scanf("%lld %lld", &pos[i], &w[i]) != 2) return 0;
        s[i] = s[i - 1] + w[i];
    }
    ll total = s[n];
    auto outside = [&](int l, int r) { return total - (s[r] - s[l - 1]); };

    const ll INF = LLONG_MAX / 4;
    vector<vector<ll>> f(n + 2, vector<ll>(n + 2, INF));
    f[c][c] = 0;
    for (int len = 2; len <= n; len++)
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            ll best = INF;
            if (f[l + 1][r] < INF)
                best = min(best, f[l + 1][r] + (pos[l + 1] - pos[l]) * outside(l + 1, r));
            if (f[l][r - 1] < INF)
                best = min(best, f[l][r - 1] + (pos[r] - pos[r - 1]) * outside(l, r - 1));
            f[l][r] = best;
        }
    printf("%lld\n", f[1][n]);
    return 0;
}

// ✗ P1220 的第三版：耗电算成了「**已经关掉**那一段的功率」。
//
// 状态和转移都写对了，只有一处：乘上去的应该是**区间外还亮着的**灯的总功率，
// 这一版乘的是**区间内**（已经关掉的）那些 —— 正好反了。
//
// ★ 它算的是一道**镜像**的题：「灯关掉之后才开始耗电」。
//   ⚠ 而官方样例挡不挡得住它，页面上量过。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int n, c;
    if (scanf("%d %d", &n, &c) != 2) return 0;
    vector<ll> pos(n + 2, 0), w(n + 2, 0), s(n + 2, 0);
    for (int i = 1; i <= n; i++) {
        if (scanf("%lld %lld", &pos[i], &w[i]) != 2) return 0;
        s[i] = s[i - 1] + w[i];
    }
    auto inside = [&](int l, int r) { return s[r] - s[l - 1]; };   // ✗ 反了

    const ll INF = LLONG_MAX / 4;
    vector<vector<array<ll, 2>>> f(n + 2, vector<array<ll, 2>>(n + 2, { INF, INF }));
    f[c][c][0] = f[c][c][1] = 0;
    for (int len = 2; len <= n; len++)
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            f[l][r][0] = min(f[l + 1][r][0] + (pos[l + 1] - pos[l]) * inside(l + 1, r),
                             f[l + 1][r][1] + (pos[r] - pos[l]) * inside(l + 1, r));
            f[l][r][1] = min(f[l][r - 1][1] + (pos[r] - pos[r - 1]) * inside(l, r - 1),
                             f[l][r - 1][0] + (pos[r] - pos[l]) * inside(l, r - 1));
        }
    printf("%lld\n", min(f[1][n][0], f[1][n][1]));
    return 0;
}