全体公開 > 合同練習会 > 20130323 > J アレルギーテスト

問題の概要

アレルゲンを投与し, アレルギー反応が出るか否かで, どの物質に対してアレルギーがあるかを調べる.
アレルゲンは一日一回, 一個のみ投与でき, 投与してから 日間アレルゲンが活性化し, アレルギー反応が出る.
全てのアレルギーを調べられるような, 反応結果を見ながらではない, 最短の投与の計画を作りたい.
最短で何日かかるか.

実装の方針, 注意点

...

各物質につき, 少なくとも1日は, ｢その物質のみアレルゲンが活性化する｣ような期間が必要.
bitDPする.
dp[既に調べたやつの集合][ラストで重ねてもよい日数]=最短の終了日数 なる配列を用いた.
例えば, 4, 2の順で投与した場合, 4--2-と投与し, 5日で終了し, 2の物のみが活性化するのは5日目のみなので, この後のテストを重ねてもよい日数は0.
4, 3と投与した場合は, 4--3--となり, 6日で終了し, 3の物のみが活性化するのが5, 6日目と二日間ある為, この後のテストを6日から初めて良く, 重ねてよい日数は1.

ソースコード

...

int dp[1<<20][8];
int in[21];
bool solve(){
    int k;
    cin >> k;
    if(!k) return false;
    rep(i, k) cin >> in[i];
 
    rep(A, 1<<k) rep(i, 8) dp[A][i] = INF;
    dp[0][0] = 0;
 
    rep(A, 1<<k) rep(diff, 8){
        rep(i, k) if(!(A>>i&1)){
            int nex = max(dp[A][diff]+1, dp[A][diff]-diff+in[i]);
            int nexd = nex - (dp[A][diff]+1);
            mineq(dp[A|(1<<i)][nexd], nex);
        }
    }
    int res = INF;
    rep(i, 8) mineq(res, dp[(1<<k)-1][i]);
    cout << res << endl;
 
    return true;
}
 

編集

---