【GCJ】2009_1C Problem C. Bribe the Prisoners
AtCoderの問題
Dashboard - Round 1C 2009 - Google Code Jam
参考書
難しさ(初心者目線)
・考え方*****
・実装***
・面白さ****
問題概要
・P人の囚人が一列の牢屋にいる(独房)
・あなたはQ人を解放したい
・解放する囚人は番目の牢屋にいる(1~P番目の内Q人)
・解放する順番は自由で1人ずつ
・解放する際に隣の囚人に解放がバレるので金貨を1枚渡さなければならない
・ただし、隣の隣にも伝達して伝わるので伝達する囚人全てに1枚渡す必要がある
・必要な金貨の最小値を求めよ
方針
dp[i][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(); }