Official
F - Treasure Hunting Editorial by blackyuki
大きい方から \(K\) 番目の整数を固定し、その値を \(X\) とします。
DP を用いて、\(X\) 以上の整数が書かれたマスを \(k\) 個通った時の \(X\) 以上の整数の和の最小値を各マスについて管理します。
\(1\) 回の DP の計算量は \(O(HWK)\) なので、全体の計算量は \(O(H^2W^2K)\) です。
\(X\) の書かれたマスが複数ある場合の処理に注意してください。
実装例 (C++)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < n; i++)
void chmin(ll&a,ll b){if(a>b)a=b;}
const ll inf = 1001001001001001001;
int main(){
int h, w, K; cin >> h >> w >> K;
vector<vector<int>> grid(h, vector<int>(w));
rep(i, h) rep(j, w) cin >> grid[i][j];
ll ans = inf;
for(auto y : grid) for(auto x : y) {
vector<vector<vector<ll>>> dp(K + 1, vector<vector<ll>>(h, vector<ll>(w, inf)));
if(grid[0][0] >= x) dp[1][0][0] = grid[0][0];
if(grid[0][0] <= x) dp[0][0][0] = 0;
rep(i, K + 1) rep(j, h) rep(k, w) {
if(j != h - 1){
if(i != K && grid[j + 1][k] >= x) chmin(dp[i + 1][j + 1][k], dp[i][j][k] + grid[j + 1][k]);
if(grid[j + 1][k] <= x) chmin(dp[i][j + 1][k], dp[i][j][k]);
}
if(k != w - 1){
if(i != K && grid[j][k + 1] >= x) chmin(dp[i + 1][j][k + 1], dp[i][j][k] + grid[j][k + 1]);
if(grid[j][k + 1] <= x) chmin(dp[i][j][k + 1], dp[i][j][k]);
}
}
chmin(ans, dp[K][h - 1][w - 1]);
}
cout << ans << endl;
}
bonus: \(O(H^2W^2)\)
posted:
last update: