街路灯の消灯問題

問題の概要

ある村では、一本の道に \(n\) 基の街路灯が設置されています。各街路灯には異なる消費電力があります（つまり、同じ時間あたりに消費する電力量が異なります）。張さんはこの道の途中にある街路灯のそばに住んでおり、毎朝夜明けになると一つずつこれらの街路灯を消す仕事をしています。

村の電気代を節約するため、張さんは各街路灯の位置と電力を記録しており、消灯作業もできるだけ効率的に行っています。しかし、張さんはどのような順序で街路灯を消せば最も電力を節約できるか分かりません。彼は毎朝、まず自分のいる位置にある街路灯を消し、その後左にも右にも移動しながら消灯作業を続けます。

当初、張さんは左側の街路灯の総電力と右側の街路灯の総電力を計算し、電力が大きい側から消していけば良いと考えていました。しかし、途中で方向転換することでさらに節約できる場合があることが判明しました。

現在、張さんの移動速度は \(1m/s\) で、各街路灯の位置（道の起点からの距離を表す整数、単位：\(m\)）と電力（\(W\)）が与えられています。街路灯を消すにかかる時間は無視できるほど短いものとします。

張さんのためのプログラムを作成し、彼が最初に街路灯を消し始めてからすべての街路灯が消えるまでの総消費電力量を最小化する消灯順序を求めてください（街路灯が消えた後は電力を消費しません）。

入力形式

最初の行には2つの数字 \(n\)（街路灯の総数）と \(c\)（張さんがいる位置の街路灯番号）が与えられます。

次の \(n\) 行には、それぞれ2つのデータが与えられます。これは第1番目から第n番目までの街路灯の位置と電力を表します。データは街路灯の位置が単調増加することが保証されています。

出力形式

最小の消費電力量（単位：\(J\)、\(1J=1W\times s\)）を1つ出力します。

入出力の例

入力

5 3
2 10
3 20
5 20
6 30
8 10

出力

270

解説/ヒント

例の解説

この場合の消灯順序は \(3,4,2,1,5\) です。

データの範囲

\(1\leq n\leq 50\)、\(1\leq c\leq n\)。

アプローチ

まず、これは線形の問題です。単純な線形DPでは状態の保存が難しいため、区間DPを考えます。

張さんがi番目からj番目までの街路灯を消し終えた後、どの位置にいるかを考慮する必要があります。そのため、次元を一つ追加し、張さんの現在位置を表します。

\(dp[i][j][0]\) は、張さんがi番目からj番目までの街路灯を消し終えた後、i番目の位置にいる場合の最小消費電力量を表します。

\(dp[i][j][1]\) は、張さんがi番目からj番目までの街路灯を消し終えた後、j番目の位置にいる場合の最小消費電力量を表します。

これにより、動的計画法の遷移方程式を導出できます：

\(dp[i][j][0]=min(dp[i+1][j][0]+Time(i,i+1,i,j+1),dp[i+1][j][1]+Time(i,j,i,j+1))\)

これは、張さんがi+1番目の位置からi番目の位置に移動する場合、およびj番目の位置からi番目の位置に移動する場合の消費電力量を計算し、その最小値を取ることを意味します。

\(dp[i][j][1]=min(dp[i][j-1][0]+Time(i,j,i-1,j),dp[i][j-1][1]+Time(j-1,j,i-1,j))\

これは、張さんがj-1番目の位置からj番目の位置に移動する場合、およびi番目の位置からj番目の位置に移動する場合の消費電力量を計算し、その最小値を取ることを意味します。

コード

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

const int MAXN = 55;
int n, start_pos;
struct StreetLight {
    int position;
    int power;
} lights[MAXN];
int prefix_sum[MAXN];
int dp[MAXN][MAXN][2];

int calculate_energy(int from_left, int from_right, int left_bound, int right_bound) {
    // 未消灯の街路灯が消費する電力量を計算
    int distance = abs(lights[from_right].position - lights[from_left].position);
    int active_lights = prefix_sum[left_bound - 1] + (prefix_sum[n] - prefix_sum[right_bound]);
    return distance * active_lights;
}

int main() {
    // DPテーブルを大きな値で初期化
    for (int i = 0; i < MAXN; i++) {
        for (int j = 0; j < MAXN; j++) {
            dp[i][j][0] = INT_MAX;
            dp[i][j][1] = INT_MAX;
        }
    }
    
    cin >> n >> start_pos;
    for (int i = 1; i <= n; i++) {
        cin >> lights[i].position >> lights[i].power;
        prefix_sum[i] = prefix_sum[i - 1] + lights[i].power;
    }
    
    // 初期状態：開始位置のみ消灯済み
    dp[start_pos][start_pos][0] = 0;
    dp[start_pos][start_pos][1] = 0;
    
    // 区間の長さを拡張しながらDPを計算
    for (int length = 2; length <= n; length++) {
        for (int i = 1; i + length - 1 <= n; i++) {
            int j = i + length - 1;
            
            // 左端に到達した場合の遷移
            int from_left_center = dp[i + 1][j][0] + 
                                  calculate_energy(i, i + 1, i, j + 1);
            int from_right_center = dp[i + 1][j][1] + 
                                   calculate_energy(i, j, i, j + 1);
            dp[i][j][0] = min(from_left_center, from_right_center);
            
            // 右端に到達した場合の遷移
            from_right_center = dp[i][j - 1][1] + 
                                calculate_energy(j - 1, j, i - 1, j);
            from_left_center = dp[i][j - 1][0] + 
                               calculate_energy(i, j, i - 1, j);
            dp[i][j][1] = min(from_left_center, from_right_center);
        }
    }
    
    // 最終結果：全区間を消灯した後の位置に関わらず最小値を取る
    cout << min(dp[1][n][0], dp[1][n][1]) << endl;
    
    return 0;
}