题解 [ABC227F] Treasure Hunting

简单 DP，当时赛时没做出来，怎么回事呢。

在 DP 过程中并不好维护前 \(k\) 大都是什么，没有办法把它放到状态里，因此我们枚举第 \(k\) 大数的下标 \(a_{x,y}\)。

然后就好办了，设 \(dp_{i,j,t}\) 表示从 \((1,1)\) 走到 \((i,j)\)，且路径上有 \(t\) 个数在前 \(k\) 大中时的答案。

有两种转移：

• 当 \(a_{i,j}\ge a_{x,y}\) 时，\(a_{i,j}\) 可以在前 \(k\) 大中，转移为 \(dp_{i,j,t}=\min\{dp_{i-1,j,t-1},dp_{i,j-1,t-1}\}+a_{i,j}\)。
• 当 \(a_{i,j}\le a_{x,y}\) 时，\(a_{i,j}\) 可以不在前 \(k\) 大中，转移为 \(dp_{i,j,t}=\min\{dp_{i-1,j,t},dp_{i,j-1,t}\}\)。

取每一个 \(a_{x,y}\) 时的 \(dp_{n,m,k}\) 最小值即可。

// Problem: F - Treasure Hunting
// Contest: AtCoder - KEYENCE Programming Contest 2021 (AtCoder Beginner Contest 227)
// URL: https://atcoder.jp/contests/abc227/tasks/abc227_f
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=(y);x<=(z);x++)
#define per(x,y,z) for(ll x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const ll N = 35, inf = 0x3f3f3f3f3f3f3f3fll;

ll n, m, k, a[N][N], dp[N][N][2*N], ans = inf;
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

int main() {
	scanf("%lld%lld%lld", &n, &m, &k);
	rep(i, 1, n) rep(j, 1, m) scanf("%lld", &a[i][j]);
	rep(x, 1, n) {
		rep(y, 1, m) {
			memset(dp, 0x3f, sizeof(dp));
			dp[0][1][0] = 0;
			rep(i, 1, n) {
				rep(j, 1, m) {
					if(a[i][j] >= a[x][y]) {
						rep(t, 1, k) {
							chkmin(dp[i][j][t], dp[i-1][j][t-1] + a[i][j]);
							chkmin(dp[i][j][t], dp[i][j-1][t-1] + a[i][j]);
						}
					}
					if(a[i][j] <= a[x][y]) {
						rep(t, 0, k) {
							chkmin(dp[i][j][t], dp[i-1][j][t]);
							chkmin(dp[i][j][t], dp[i][j-1][t]);
						}
					}
				}
			}
			chkmin(ans, dp[n][m][k]);
		}
	}
	printf("%lld\n", ans);
	return 0;
}