競プロ日記

プロコン参加記録とか解いた問題とか

【GCJ】2009_1C Problem C. Bribe the Prisoners

AtCoderの問題

Dashboard - Round 1C 2009 - Google Code Jam

参考書

プログラミングコンテストチャレンジブック [第2版]

難しさ(初心者目線)

・考え方*****

・実装***

・面白さ****

問題概要

・P人の囚人が一列の牢屋にいる(独房)
・あなたはQ人を解放したい
・解放する囚人は{a_1,a_2,\dots,a_q}番目の牢屋にいる(1~P番目の内Q人)
・解放する順番は自由で1人ずつ
・解放する際に隣の囚人に解放がバレるので金貨を1枚渡さなければならない
・ただし、隣の隣にも伝達して伝わるので伝達する囚人全てに1枚渡す必要がある
・必要な金貨の最小値を求めよ

方針

dp[i][j]:={a_i}番目の牢屋と{a_j}番目の牢屋の間にいる解放したい囚人を解放する(両端は含まない)時に必要な金貨の最小値とする.
簡単のために0番目とP+1番目の牢屋を追加する.
dp[k][k+1]は間に1人も解放したい囚人がいないので0である.
まずはdp[k][k+2]から考えていく.
また最初に解放する囚人は何番目でも同じである.

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

int P,Q;
int A[100+2];//両端追加

int dp[101][102];
void solve(){
    //幅が1以下の時は0
    FOR(i, 0, Q+1) dp[i][i+1] = 0;
    //幅
    FOR(w, 2, Q+2){
        //左端
        for(int i=0; i+w<=Q+1; ++i){
            //右端
            int j = i + w;
            //2番目以降で解放に必要な金貨
            int t = 99999999;

            //全探索
            for(int k=i+1; k<j; ++k){
                t = min(t, dp[i][k]+dp[k][j]);
            }

            //i-jの間の1人目の囚人を解放するのに必要な金貨は場所によらない
            dp[i][j] = t + A[j] - A[i] - 2;
        }
    }
    cout << dp[0][Q+1] << endl;;
}

int main(){
    cin >> P >> Q;
    A[0] = 0;
    A[Q+1] = P + 1;
    FOR(i, 1, Q+1) cin >> A[i];
    solve();
}