ABC175 E - Picking Goods (500)
$ dp[i][j][k] でi行j列目にいてその行でk回アイテムを拾った時の価値の最大値とする
簡単にするためにアイテムの無いマスにも価値が0のアイテムがあることにする
基本的な遷移はdp[i][j][k] = max(*max_element(all(dp[i-1][j])), dp[i][j-1][k]);
$ K \gt 0ならそのマスでもアイテムを拾えるので、chmax(dp[i][j][k], max(*max_element(all(dp[i-1][j])), dp[i][j-1][k-1]) + b[i][j]);
$ dp[r-1][c-1 の配列内での最大値が答え
各マスについてのアップデートは定数時間なので$ O(RC)