P5989题解

zhangzihang · 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;
}