Codeforces 82D: Two out of Three

Problem - D - Codeforces

Difficulty: 2000

問題概要

待ち行列を考える．今N人の人が一列に並んでいて，レジにてサービスを受ける時間待ちをしている．ある人iがサービスを受け終わるのにかかる時間はAiである．このレジは先頭3人の内，2人選んで同時に捌くことができる．このときにかかる時間は，2人の人をそれぞれi，jとすると，max(Ai，Aj)である．全員がサービスを受け終わるのに，どのような捌き方をすればよいか

N < 1000

解法

重要な観察として，ある時点でまだサービスを受けていない人の集合は，番号が若い人iと，人j(>i)以降の人全員と表されることがわかる．ただし1人の場合は例外であるので，注意する．よって現在の列の状態は２つの数字iおよびjで一意に表すことができる．そこで，次のようなDPを考える．

dp[i][j] := 今列に残っているのが人iと，j(>i)以降の人全員であるとき，彼らを全員捌くために必要な最小のコスト

遷移は，

1) i番目とj番目の人を捌いてから残りはdp[j+1][j+2]

2) i番目とj+1番目の人を捌いてから残りはdp[j][j+2]

3) j+1番目とj+2番目の人を捌いてから残りはdp[i][j+2]

の3つである．

const int MAX_N = 1010;

int dp[MAX_N][MAX_N] = {}; // i番目の人が残っていて，j(>i)からNまでの人が残っているときの最小コスト

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    VI A(N); REP(i,N) cin >> A[i];

    if(N==1){
        cout << A[0] << endl;
        cout << 1 << endl;
        return 0;
    }

    dp[N-1][N] = A[N-1];
    dp[N-2][N-1] = max(A[N-2],A[N-1]);
    dp[N-2][N] = A[N-2];

    for(int i = N-3; i >= 0; i--){
        for(int j = N; j >= i+1; j--){
            if(j == N) dp[i][j] = A[i];
            else if(j == N-1) dp[i][j] = max(A[i],A[N-1]);
            else{
                int t1 = max(A[i],A[j]) + dp[j+1][j+2];
                int t2 = max(A[i],A[j+1]) + dp[j][j+2];
                int t3 = max(A[j],A[j+1]) + dp[i][j+2];
                dp[i][j] = min({t1,t2,t3});
            }
        }
    }

    cout << dp[0][1] << endl;

    //復元パート
    int left = 0;
    int right = 1;
    REP(i,(N+1)/2){
        if(right == N){
            cout << left+1 << endl;
            return 0;
        }

        if(dp[left][right] - dp[right+1][right+2] == max(A[left],A[right])){
            cout << left+1 << " " << right+1 << endl;
            left = right+1;
            right = right+2;
        }else if(dp[left][right] - dp[right][right+2] == max(A[left],A[right+1])){
            cout << left+1 << " " << right+2 << endl;
            left = right;
            right = right+2;
        }else{
            cout << right+1 << " " << right+2 << endl;
            right = right+2;
        }
    }
}