题解：P5989 [PA 2019] Wina
xch_nailong
·
·
题解
题目简述
要求：
- **正好**选 $k$ 个数。
- 选走的数中的最小值应尽量小。
- 一个数只有它左上角和右上角的数**都**被选走（或没有）时才能被选。
# 题目分析
设 $f_{i,j}$ 表示要选 $a_{i,j}$ 最少需要选多少个点。
以样例为例，$f$ 数组是这样子的：
可以发现，$f$ 数组的求法为：$f_{i,j} = (i - j + 1) \times j$。
求完 $f$ 数组后，直接在满足 $f_{i,j} \leq k$ 中所有 $a_{i,j}$ 中取 $\min$ 就可以了。
# 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, k, a[2001][2001], f[2001][2001], ans = 2e9;
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
scanf("%d", &a[i][j]);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
f[i][j] = (i - j + 1) * j;
// cout << f[i][j] << ' ';
}
// cout << '\n';
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
if (f[i][j] <= k) {
ans = min(ans, a[i][j]);
}
}
}
printf("%lld", ans);
return 0;
}
```