チーム戦 [yukicoder No.710]

https://yukicoder.me/problems/no/710

前提知識

• 動的計画法

解法

https://yukicoder.me/submissions/270352

動的計画法をしていく。
dp[i][d] := i番目まででd=(Bさんの累計時間-Aさんの累計時間)のときのかかる時間の最小値
まず、このDPではdが負の数になる場合があり得る。
このように添え字が負の数になるような場合はd=0をずらして格納しておく。
baseを0として考える。つまり、
dp[i][j] := i番目まででd=(Bさんの累計時間-Aさんの累計時間)のときのかかる時間の最小値（j = d + base）
として計算していこう。
　
遷移がややこしいのだが、基本的には
1. 累計時間の差が広がるときは全体でかかる時間が伸びる
2. 累計時間の差が縮まるときは全体でかかる時間は変化しない
3. BさんとAさんの累計時間の大小が入れ替わるときは、全体でかかる時間が差分だけ増える
の3つの遷移をAさんに割り当てた、Bさんに割り当てたとき、のそれぞれについて行えば良い。
この遷移をバグ無しで無くのは大変。

int N, A[101], B[101];
int dp[101][204010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i] >> B[i];

    rep(i, 0, 101) rep(j, 0, 204010) dp[i][j] = inf;
    int base = 101010;
    dp[0][base] = 0;

    rep(i, 0, N) rep(j, 1010, 200010) {
        int d = j - base, dd;
        
        // get A
        dd = d - A[i];
        if (0 < d and dd < 0) chmin(dp[i + 1][dd + base], dp[i][j] + abs(dd)); // 3
        else if(d <= 0) chmin(dp[i + 1][dd + base], dp[i][j] + A[i]); // 1
        else chmin(dp[i + 1][dd + base], dp[i][j]); // 2

        // get B
        dd = d + B[i];
        if (0 <= d) chmin(dp[i + 1][dd + base], dp[i][j] + B[i]); // 1
        else if (d < 0 and 0 <= dd) chmin(dp[i + 1][dd + base], dp[i][j] + dd); // 3
        else chmin(dp[i + 1][dd + base], dp[i][j]); // 2
    }

    int ans = inf;
    rep(j, 0, 204010) chmin(ans, dp[N][j]);
    cout << ans << endl;
}