2022年8月17日
本日お日柄以下略
DPやってくヨ
保身
解説っていうか、頭の流れを書いてる感じなので厳密もくそもない。
でも解ければ正義の派閥なので良し。俺は強い。
4次元DP書くのが初めてなので、楽できるところ楽してないし、関数化とかもしていない。
ポエムなつもりで読んでね♡
[4次元DP]
-
問題文のようなもの
- H行W列のグリッドがある
- 0行0列(0,0) から、 H-1行W-1列(H-1,W-1)に移動することを考える。
- 各マスは0,1で構成されている。
- 移動は同じ数字の間でしか移動できない
でもって
- 各行、各列に対してお金を払って0と1を反転することが出来る
- 最小のお金で(0,0)->(H-1,W-1)への移動をしろ
-
-
制約
なるほどね同じ行や列に対して2回操作を行うのは無駄でしかないらしい。というのも2回同じ行に対して操作を行っても、その行の各マスは結局操作の前後で変化がなく、ただお金を払うだけだから
ということで、全探索的な解法が浮かんでくる。
-
各行、各列は操作を行うか行わないかの2通り
-
じゃあBIT全探索でもしてみるか❓
- 無理
- 行が2000個、列が2000個の計4000個なので、24000通りになってしまって、さすがに全探索は無理
-
ちょっと考えてみると、ある程度移動したとき、今いるマスより左上に対しての変更を行う操作はしなくていい
-
どういうことかっていうと、なんやかんやあって下のような盤面にできたとする
-
-
この状態の盤面にして、今☆の地点(1,1)まで移動したとすると、0行目と0列目に対しては、もう操作を行わなくていい。ということが分かる。
- 左や上への移動を行えないから、操作を行うだけお金の無駄、ということもあるが、
- そもそも、左上への操作を行ってしまうと、「お前どうやって☆の位置まで移動してきたねん」みたいな感じになっちゃう
-
って感じで、以上のようなことを考えてみると、DP的解法が使えるんじゃないかな~っていうのが感覚で湧いてくる
-
DPで解くとして、
DP[i][j]:=(i,j)まで移動するときの最小コスト みたいな感じでやるのかなって思うけど、同じ行や列に対して2回操作を行うことはできない(しない)ので、行や列に対して操作を行ったかどうかっていうのもDPの状態として持たせないといけない
-
んじゃまあ、行と列の状態が欲しいから、2次元ぐらい増やせばいいのかな
-
DP[i][j][x][y]:=(i,j)まで移動するときの最小コスト。ただし、x=1の時、行iに対して操作を行っている。y=1の時列jに対して操作を行っている。
-
こんな感じでやればいけそうやな
- xとyの取りうる値は2通りで、状態としては(x,y) = {(0,0), (0,1), (1,0), (1,1)}だけだよ
で、DPの定義はまあいいとして、これ遷移(移動)をどうやって行うかが難しそうだね
たとえば、(i,j,x,y) = (2,3, 0,0)だとして、これは2行3列にいて、2行目に対しても3列目に対しても操作を行っていないということになる。この状態からの移動を考える。

-
で、次は、
S[0][0]じゃないふうに経路を作った場合の最小値も求める
-
DPテーブルの初期化をもう一回。
-
rep(i,2010)rep(j,2010)rep(x,2)rep(y,w)dp[i][j][x][y] = INF;
//dp[i][j][x][y]:= (i,j)
dp[0][0][0][1] = C[0];//S[0][0]じゃない方にするので、行に対する操作か、列に対する操作を最初のマスにしとかないといけない
dp[0][0][1][0] = R[0];
now = 1-now;
-
rep(i,h){
rep(j,w){
bool same = (now == S[i][j+1]);
bool same2 = (now == S[i+1][j]);
rep(x,2){
rep(y,2){
// dp[i][j][x][y]からの繊維
if((same && x) || (!same && !x)){
chmin(dp[i][j+1][x][1], dp[i][j][x][y] + C[j+1]);
} else {
chmin(dp[i][j+1][x][0], dp[i][j][x][y]);
}
if((same2 && y) || (!same2 && !y)){
chmin(dp[i+1][j][1][y], dp[i][j][x][y] + R[i+1]);
}else {
chmin(dp[i+1][j][0][y], dp[i][j][x][y] );
}
}
}
}
}
rep(x,2)rep(y,2){
chmin(ans,dp[h-1][w-1][x][y]);
}
cout << ans << endl;
- 中身のコードはさっきと全く一緒なのでうえのコードは読まなくていい(多分)
-
終わり
日記
今日は、ハンバーグを食いにインスタで見つけた店に行ったら、OPENと書かれているが品切れだった。
勘弁してくれ