実装上の注意
同じ場所で2回釣らないこと．
(今のマスで釣ったか) \(\in Bool\) で管理した．
遷移に注意すれば，このフラグは無くてもDPは可能． その場合，(移動2種類)x(移動先で釣るor釣らない)の4通りの遷移になる． 移動先で釣るかどうかを決めるのが大事．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
ll dp[220][110][110][2];
int main() {
ll h,w; cin >> h >> w;
vvll a(h, vll(w));
cinvv(a);
dp[0][0][0][0] = 0;
rep(k,h+w){
rep(x,h) rep(y,w){
rep(f,2){ // 今のマスで釣ったか
ll now = dp[k][x][y][f];
if(x+1 < h) chmax(dp[k][x+1][y][0], now);
if(y+1 < w) chmax(dp[k][x][y+1][0], now);
if(!f) chmax(dp[k+1][x][y][1], now + a[x][y]);
}
}
}
rep1(k,h+w-1){
ll ans = 0;
rep(f,2) chmax(ans, dp[k][h-1][w-1][f] );
cout << ans << endl;
}
return 0;
}
