自动搬运

查看原文

来自洛谷，原作者为

	zhangzihang 一只啥也不是的蒟蒻（AFOed

搬运于2025-08-24 22:16:15，当前版本为作者最后更新于2022-10-25 13:49:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

题目大意

• 给定一个 $n,k$，以及一个 $a$ 数组。
• 要求拿走 $k$ 个数，使得拿到的所有数种最小的数最小。
• 只有左上，右上都没有数或已被取走该数才能被取到。

我们来分析一下方法，我们要在 $\dfrac{n(n+1)}{2}$ 个数中找到最小的数，而且满足取到该点时总共取得数 $s \le k$ 我们可以考虑建立一个数组 $f_{i,j}$，表示取到点 $a_{i,j}$。时取的最少点的个数。

稍微分析一下样例我们可以发现 $f_{i,j}=(i-j+1)\times j$。

所以代码如下：

#include<bits/stdc++.h>
using namespace std;
int a[2005][2005],f[2005][2005]; // f[i][j]表示取到第i,j个点的最少次数 
int main(){
	int n,k;cin>>n>>k;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
			cin>>a[i][j];
	dp[1][1]=1;
	for(int i=2;i<=n;i++)  //计算f数组 
		for(int j=1;j<=i;j++)
			f[i][j]=(i-j+1)*j;
	int ans=2020;
	for(int i=1;i<=n;i++) //遍历所有点找到取到该点次数小于等于k的最小值点 
		for(int j=1;j<=i;j++)
			if(f[i][j]<=k)
				ans=min(ans,a[i][j]);
	cout<<ans; 
	return 0;
}