square869120Contest #3 D - お土産購入計画2 / Souvenirs (600)
解法
- 最短路なので2人とも(0,+1) or (+1,0) で進む
- 1人だったら? -> DPで(x,y)または(何回進んだか,x)をキーとして持ってやればできる
- なぜなら(x,y)で最大のお土産を持つためには(x-1,y)or(x,y-1)で最大のお土産を持っている必要があるため
- 2人でも2人の座標を持ってやればできそう
- (x,y)両方とも持つ必要はなく, (ターン数,1人目のx,2人目のx) を持てばOK
- 漸化式は
- 2人とも同じとこにいく(nx,ny)=>+a[nx][ny]
- 2人が別のとこにいく(nx1,ny1),(nx2,ny2) => +a[nx1][ny1]+a[nx2][ny2] でOK
メモ
1人ならDPできるねーからマップを2つに分けて各々DPするか?みたいな方向に行ってしまってできなかった.
どういう状態を持つべきか,とかの訓練が足りなさそう
