洛谷P2409 Y的积木

- 77通过
- 491提交
题目提供者zhouyonglong
标签云端评测
难度普及+/提高

讨论题解

题目背景

Y是个大建筑师，他总能用最简单的积木拼出最有创意的造型。

题目描述

Y手上有n盒积木，每个积木有个重量。现在他想从每盒积木中拿一块积木，放在一起，这一堆积木的重量为每块积木的重量和。现在他想知道重量和最小的k种取法的重量分别是多少。（只要任意更换一块积木，就视为一种不同的取法。如果多种取法重量总和一样，我们需要输出多次。）

输入输出格式

输入格式：

第一行输入两个整数，n,k，意义如题目所描述。

每组数据接下来的n行，第一个整数为mi，表示第i盒积木的数量，在同一行有mi个整数，分别表示每个积木的重量。

输出格式：

一行，重量最小的k种取法的重量，要求对于每个数据，从小到大输出

输入输出样例

输入样例#1：

输出样例#1：

3 4 5 5 6 6 7 7 7 7

说明

对于30%的数据：2<=mi<=10,1<=n<=10

对于50%的数据：2<=mi<=50,1<=n<=50

对于100%的数据：2<=mi<=100,1<=n<=100,1<=k<=10000,每个积木的重量为不超过100的正整数，所有mi的积大于等于k。本题不卡常。

分析：显然搜索对于本题的数据而言是不行的，然后想到了一道题目，给你两个序列，从每个中选一个数相加，求和最小的k个，显然可以利用优先队列（小根堆）维护，但是对于本题而言较难维护，考虑dp.

一开始想的是根据题目给的数据来定状态，设f[i][j]为前i盒积木中第j小的方案，但是不知道怎么继续转移，换一种表示状态的方法.一般而言，计算的结果是不能充当状态的，例如j(可能表示不好)，那么我们可以设f[i][j]为前i盒积木中重量为j的方案数，这样就避免了算第j小，那么f[i][j] = Σf[i-1][j-w[i][k]],w[i][k]为第i盒积木中第k个积木的重量，如果直接枚举的话不能过，还需要优化一下枚举的范围.计算出n盒积木中的最大和和最小和再枚举即可.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int n, k, w[105][105], f[105][10010], sizee[105], minnum,maxnum, sum;

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
    {
        int m;
        scanf("%d", &m);
        int minn = 1000000000,maxx = 0;
        for (int j = 1; j <= m; j++)
        {
            scanf("%d", &w[i][j]);
            minn = min(w[i][j], minn);
            maxx = max(w[i][j], maxx);
            sum += w[i][j];
        }
        minnum += minn;
        maxnum += maxx;
        sizee[i] = m;
    }
    f[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= sizee[i]; j++)
            for (int kk = w[i][j]; kk <= maxnum; kk++)
                if (f[i][kk] <= k && f[i - 1][kk - w[i][j]] <= k)
                    f[i][kk] += f[i - 1][kk - w[i][j]];
                else
                    f[i][kk] = k;

    int kk = 0;
    for (int i = minnum; i <= sum; i++)
        if (f[n][i])
            for (int j = 1; j <= f[n][i]; j++)
            {
                kk++;
                if (kk > k)
                    return 0;
                printf("%d ", i);
            }

    return 0;
}