题解：B4567 [山东省小学组体验营 2026] 精选矿石

xiaozhengguoaaa · 2026-08-04 17:40:16 · 题解

小学组是偏爱背包吗。

主要思路

注意到题目里说了，最轻的和最重的矿石重量相差不超过 10，这不难发现。

设所有矿石中的最轻重量为 minn。

对每块矿石，计算偏移量 d = w - minn，显然 0 \le d \le 10。

这样，如果我们最终选了 j 块矿石，那么它们的总重量为：

定义 f_{i,j,k} 表示考虑前 i 块矿石，恰好选了 j 块，偏移量之和为 k 时的最大总价值。

转移为：

• 不选第 i 块矿石：

• 选第 i 块矿石（还要满足 j \ge 1 且 k \ge d_i）：

遍历所有 j 和 k，若 j \cdot minn + k \le m，则更新答案：

最终输出 \text{ans}。

时间复杂度为 O(n^2 \cdot 1000)。

:::info[AC code]

#include <bits/stdc++.h>
#define int long long
#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 4e6 + 7;
const int P = 1e9 + 7;
const int MOD = 998244353;
const int INF = 0X3F3F3F3F;
// const int dx[] = {-1, 1, 0, 0, -1, -1, +1, +1};
// const int dy[] = {0, 0, -1, 1, -1, +1, -1, +1};
const int dx[] = {-1 , 1 , 0 , 0} ;
const int dy[] = {0 , 0 , -1 , 1} ;
int dp[105][105][1005] ;
int n , m ;
int w[N] , v[N] ;
int minn = 1e18 ;
int ans ;
int sum ; 
signed main()
{
    fst ;
    cin >> n >> m ;
    for (int i = 1 ; i <= n ; i ++)
    {
        cin >> w[i] >> v[i] ;
        minn = min(minn , w[i]) ;
    }
    for (int i = 1 ; i <= n ; i ++)
    {
        w[i] = w[i] - minn ;
    }
    memset(dp , -INF , sizeof(dp)) ;
    dp[0][0][0] = 0 ;
    for (int i = 1 ; i <= n ; i ++)
    {
        for (int j = 0 ; j <= i ; j ++)
        {
            for (int k = 0 ; k <= 1000 ; k ++)
            {
                dp[i][j][k] = max(dp[i][j][k] , dp[i - 1][j][k]) ;
                if (j >= 1 && k >= w[i])
                {
                    dp[i][j][k] = max(dp[i][j][k] , dp[i - 1][j - 1][k - w[i]] + v[i]) ;
                }
            }
        }
    }
    for (int i = 0 ; i <= n ; i ++)
    {
        for (int j = 0 ; j <= 1000 ; j ++)
        {
            if (i * minn + j <= m)
            {
                ans = max(ans , dp[n][i][j]) ;
            }
        }
    }
    cout << ans ;
    return 0 ;
}

:::