JOI-レベル6を解いた
JOI-レベル6を解いた
とりあえずレベル6の予選本選問題を解いたのでメモ
おせんべい
横の数が最大10行なので、行を回転させる組み合わせは1024通りのみ
これは全探索でいける
あとは列の回転方法だが,
白が多い->回転させない
黒が多い->回転させる
というふうにすればよい
これでAC
ダーツ
DPは点数の合計が大きすぎるので無理と判断
投げないという判断は、点数が0ということと同義なので
4本絶対投げるが的に0点という枠がある、と考えて良い
これで考えやすくなったので、あとは２本投げた結果を２つ組み合わせればいい
組み合わせる方法
1.最初の２本の点数をvとする
2.M-v以下の数を探す(2分木で探す)
3.足す
これの最大値を取ればいい
連鎖
ぷよぷよやん
1.一個変える部分を決める(index..iとする)
2.その隣の色にする(i-1,i+1の色)
3.int rec(i-1,i)と進めていく
再帰は中身見たらわかるはず
ピザ
店の場所は,D={0,d2,d3,...,dn,d}としたほうが考えやすい
1.届け先をkとする
2.Dの中でk以上で一番小さい数をrとする
3.Dの中でk以下で一番大きい数をlとする
4.min(k - l, r - k)が一番近い店からの距離である
これの総和を求めればいい
通勤経路
下からくる場合、左からくる場合と条件を分ければいいですね
つらら
車の中でやったやつですね...
折れるつららをqueueに突っ込んでいき、順番に計算させていきます
つららを折ったら隣が折れるかどうかチェックしていく
つららが折れ始める時間は隣の折れた時間なので,それも記録していきます
古本屋
本はジャンル分けして、値段の高い順にソートしておきます
ソートしたものを１冊,2冊,,,とセットにした値段をboxに入れておきます
後は
FOR(k,1,boxs[i].size() - 1) { if(j - k >= 0) { dp[i][j] = max(dp[i][j],dp[i - 1][j - k] + b[i][k] + k * (k - 1)); } }
というふうにdpしてやればおｋ
イルミネーション
この問題の図の外側を１マス広げると考えやすい
1.建物の外にあるマスをマーキングしていく
2.建物のマスをたどっていく
3.建物のマスの外側のマスが1でマーキングしたマスであれば,resultを1加算する(建物の外から見える壁であるため)
幅優先で解けますね
夜店
SをまたがないようにDPする
電飾
交互になっている部分はまとめて変えたほうがいい
色が交互になっている場所を探し。右側の色と左側の色と長さを覚えておく
考えるのは、右側の色と左側の色が違うかどうかで長さが変わる
うまく説明できないなぁ
部活のスケジュール表
ビットdp
dp[i][j]:=i日目がjという組み合わせで参加した時の組み合わせ数
責任者がいるか、カギを持つ人がいるかをチェックしていく
JOI紋章
まず初期での紋章の数を数える
正方形を変えた時に影響を受けるのは一部なので,そこだけ計算させればいよい
IOI饅頭
dp[i][j]:=箱をi種類まで選び饅頭をj個入れる場合に必要な箱の値段
あとは饅頭を大きい順に入れてみるだけ
ケーキの切り分け2
区間DPを勉強しました
オレンジの出荷
よく覚えていない...
もう一回解こうかな
スタンプラリー2
Jは先頭に、Iは後端に置くべき
組み合わせの計算方法が大切ですね
最後の方グダってますね...
