問題文

動的計画法の問題を考察します。便宜上、問題文中の費用係数を\\(v_i\\)で表現します。

\\(f_i\\)を第\\(i\\�\\)位置までの最適解と定義します。各遷移は、\\(i\\)番目に区間\\([j+1,i]\\)のコストを追加する操作です。

明らかに、累和を用いて最適化できます。しかし\\(s\\)の存在により、直接次元を追加してグループ数を記録すると大きなオーバーヘッドが発生します。以下に\\(n^3\\)のアルゴリズムの方程式を示します：

この方程式には多くの不要な状態が含まれており、最終的には1つの位置での最適解だけを求める必要があります。

逆の考え方に転換すると、各グループ化は時間を\\(s\\)だけ遅延させるため、事前にその影響値を加算すればよいことがわかります。

つまり、\\(k\\)グループに分割する場合、すでに\\(k\\)回の\\(s\\)による影響値が加算されています。具体的には\\(s \times \sum_{l=j+1}^n v_l\\)です。

以下に時間計算量\\(\mathcal{O}(n^2)\\)の遷移方程式を示します：

すべての累和を累和配列で管理し、実装を進めます。

実装コード

#include 
using namespace std;
const int MAXN = 5007;
int N, S, T[MAXN], V[MAXN];
long long F[MAXN];

int main() {
    scanf("%d%d", &N, &S);
    for(int i = 1; i <= N; ++i) {
        scanf("%d", &T[i]);
        T[i] += T[i-1];
        scanf("%d", &V[i]);
        V[i] += V[i-1];
    }
    
    memset(F, 0x3f, sizeof F);
    F[0] = 0;
    
    for(int i = 1; i <= N; ++i)
        for(int j = 0; j < i; ++j) {
            F[i] = min(F[i], F[j] + (long long)T[i] * (V[i] - V[j]) + (long long)S * (V[N] - V[j]));
        }
    
    printf("%lld\n", F[N]);
    return 0;
}

傾き最適化によるO(n)解法

上記はP2365の\\(\mathcal{O}(n^2)\\)解法です。次に、この問題の\\(\mathcal{O}(n)\\)傾き最適化DPを紹介します。

注: 以下の説明では、\\(sumt_i \gets \sum_{j=1}^i t_j\\)、\\(sumv_i \gets \sum_{j=1}^i v_j\\)とします。

元の方程式から\\(\min\\)を取り除くと：

展開し、項を移動すると：

ヒント: 傾き最適化で項を分解する際、\\(x,y\\)は\\(j\\)に関連し、\\(k\\)は\\(i\\)に関連している必要があります。

問題は、傾き\\(k=sumt_i+s\\)の直線で、\\(y\\)軸切片が最大となる点を求めることと等価です。ここでの点は\\((sumv_j, f_j-s\times sumv_j)\\)です。

線形計画の考え方を用い、傾き\\(k=sumt_i+s\\)の直線を下から上に移動させ、最初に接触する点が最小切片を与えます。

この問題では、\\(k\\)は単調増加し、\\(x\\)は単調増加します。座標系上の点の形状は以下のようになります。

図では、線形計画で点を選択する方法では赤点は選択できません。青点で形成される幾何学的図形（凸包）を維持する必要があります。

単調キューを使用して凸包を維持します。

\\(x\\)は単調増加するため、新しい点を追加する際は常に後方になります。以下の場合を考えます。

赤点が新しく追加される点、tailがキューの末尾、tail-1がキューの末尾の一つ前の点です。この状態で新点を追加すると凸包が破壊されるため、キューの末尾の点を削除します。

毎回\\(\mathcal{O}(1)\\)で最適な点を取得するため、キューの先頭を維持します。

上図のように、キューの先頭と次の点で形成される直線の傾きが\\(k=sumt_i+s\\)より小さい場合、\\(k\\)が単調増加するため、先頭の点は今後使用されません。削除してよいです。

ヒント: 1. \\(\frac{y_1-y_2}{x_1-x_2} \leq \frac{y_3-y_4}{x_3-x_4}\\)は\\((y_1-y_2)\times(x_3-x_4) \leq (y_3-y_4)\times(x_1-x_2)\\)と変換して精度問題を回避できます。
2. 異なる問題での傾き最適化では傾きが単調減少することがあるため、別途図を分析する必要があります。

実装コード（傾き最適化版）

#include 
#define FOR(i, s, t) for(int i = (int)s; i <= (int)t; ++i)
using namespace std;
const int MAXN = 300007;
int N, Q[MAXN];
long long S, T[MAXN], V[MAXN], F[MAXN];

int main() {
    scanf("%d%lld", &N, &S);
    FOR(i, 1, N) {
        scanf("%lld%lld", &T[i], &V[i]);
        T[i] += T[i-1];
        V[i] += V[i-1];
    }
    
    int head = 0, tail = 0;
    FOR(i, 1, N) {
        while(head < tail && F[Q[head+1]] - F[Q[head]] <= (T[i] + S) * (V[Q[head+1]] - V[Q[head]]))
            ++head;
        F[i] = F[Q[head]] + T[i] * (V[i] - V[Q[head]]) + S * (V[N] - V[Q[head]]);
        while(head < tail && (F[i] - F[Q[tail]]) * (V[Q[tail]] - V[Q[tail-1]]) <= (F[Q[tail]] - F[Q[tail-1]]) * (V[i] - V[Q[tail]]))
            --tail;
        Q[++tail] = i;
    }
    
    printf("%lld\n", F[N]);
    return 0;
}

拡張問題：SDOI2012の強化版

上記は基本的な傾き最適化の実装です。次に、SDOI2012の強化版を見ていきましょう。

一見すると違いはありませんが、この問題では\\(t_i\\)が負の値を取ることができます。つまり、前述の\\(k=sumt_i+s\\)はもはや単調増加ではなくなりますが、\\(x\\)は依然として単調増加しています。

これにより、前述のようにキューの先頭を答えとして直接維持することはできませんが、キューの末尾での凸包の維持は同じです。下凸包（下に凸の凸包）の性質を観察します。

上図を注意深く観察すると、\\(k_f < k_g < k_h\\)であることがわかります。つまり、隣接する2点間の傾きは単調増加しています。

この性質を利用して、傾き\\(k \geq sumt_i+s\\)である最初の直線の次の点を二分探索で見つけ、遷移を行います。

時間計算量は\\(\mathcal{O}(n\log n)\\)です。

実装コード（強化版）

#include 
#define FOR(i, s, t) for(int i = (int)s; i <= (int)t; ++i)
using namespace std;
const int MAXN = 300007;
int N, Q[MAXN];
long long S, T[MAXN], V[MAXN], F[MAXN];

int main() {
    scanf("%d%lld", &N, &S);
    FOR(i, 1, N) {
        scanf("%lld%lld", &T[i], &V[i]);
        T[i] += T[i-1];
        V[i] += V[i-1];
    }
    
    int head = 0, tail = 0;
    int left, right, mid, res;
    FOR(i, 1, N) {
        left = head;
        right = tail;
        res = Q[right];
        while(left <= right) {
            mid = (left + right) >> 1;
            if((F[Q[mid+1]] - F[Q[mid]]) > (T[i] + S) * (V[Q[mid+1]] - V[Q[mid]])) {
                right = mid - 1;
                res = Q[mid];
            } else {
                left = mid + 1;
            }
        }
        F[i] = F[res] + T[i] * (V[i] - V[res]) + S * (V[N] - V[res]);
        while(head < tail && (F[i] - F[Q[tail]]) * (V[Q[tail]] - V[Q[tail-1]]) <= (F[Q[tail]] - F[Q[tail-1]]) * (V[i] - V[Q[tail]]))
            --tail;
        Q[++tail] = i;
    }
    
    printf("%lld\n", F[N]);
    return 0;
}