洛谷 P3265 / loj 2108 [JLOI2015]装备购买 题解【贪心】【线性基】

点击量：168

线性基思想入门题。

目录

题目描述

脸哥最近在玩一款神奇的游戏，这个游戏里有 $ n$ 件装备，每件装备有 $ m$ 个属性，用向量 $ \mathbf z_i=(a_1, \ldots ,a_j, \ldots , a_m)$ 表示 $ (1 \leq i \leq n, \ 1 \leq j \leq m)$，每个装备需要花费 $ c_i$，现在脸哥想买一些装备，但是脸哥很穷，所以总是盘算着怎样才能花尽量少的钱买尽量多的装备。对于脸哥来说，如果一件装备的属性能用购买的其他装备组合出（也就是说脸哥可以利用手上的这些装备组合出这件装备的效果），那么这件装备就没有买的必要了。

严格的定义是，如果脸哥买了 $ \mathbf z_{i_1},\ldots,\mathbf z_{i_p}$ 这 $ p$ 件装备，那么对于任意待决定的 $ \mathbf z_h$，不存在 $ b_1, \ldots ,b_p$ 使得 $ b_1\mathbf z_{i_1} + \ldots + b_p\mathbf z_{i_p} = \mathbf z_h$（$ b_i$ 均是实数），那么脸哥就会买 $ \mathbf z_h$，否则 $ \mathbf z_h$ 对脸哥就是无用的了，自然不必购买。

举个例子，$ \mathbf z_1=(1, 2, 3), \ \mathbf z_2=(3, 4, 5), \ \mathbf z_h=(2, 3, 4), \ b_1 =\frac{1}{2}, \ b_2 =\frac{1}{2}$，就有 $ b_1\mathbf z_1 + b_2\mathbf z_2 = \mathbf z_h$，那么如果脸哥买了 $ \mathbf z_1$ 和 $ \mathbf z_2$ 就不会再买 $ \mathbf z_h$ 了。

脸哥想要在买下最多数量的装备的情况下花最少的钱，你能帮他算一下吗？

输入输出格式

输入格式：

第一行两个数 $ n, m$。

接下来 $ n$ 行，每行 $ m$ 个数，其中第 $ i$ 行描述装备 $ i$ 的各项属性值。

接下来一行 $ n$ 个数，其中 $ c_i$ 表示购买第 $ i$ 件装备的花费。

输出格式：

一行两个数，第一个数表示能够购买的最多装备数量，第二个数表示在购买最多数量的装备的情况下的最小花费。

输入输出样例

输入样例 #1：

3 3
1 2 3
3 4 5
2 3 4
1 1 2

输出样例 #1：

2 2

说明

样例解释：

如题目中描述，选择装备 $ 1$ 装备 $ 2$，装备 $ 1$ 装备 $ 3$，装备 $ 2$ 装备 $ 3$ 均可，但选择装备 $ 1$ 和装备 $ 2$ 的花费最小，为 $ 2$。

对于 $ 100 \%$ 的数据, $ 1 \leq n,m \leq 500, 0 \leq a_j \leq 1000$。

题解：

强烈建议在HB前辈Sengxian的博客里学线性基！！！

首先要对这个题中的向量表示进行理解。如果 $ \mu\mathbf{a}+\lambda\mathbf{b}=\mathbf{c}(\mu,\lambda\in \mathbb{R})$，则用 $ \mathbf{a},\mathbf{b},\mathbf{c}$ 中的任意一个，就能表示出剩下一个。因此在这个题中要选择的装备的最小数量是一定的，接下来我们要考虑最小花费。

对于上面的 $ \mathbf{a},\mathbf{b},\mathbf{c}$，其实可以表示任意多种向量，假设此时只有三种，那么我们一定选择花费最便宜的两个保留下来，并剔除另外一个，因为另外一个一定可以被这两个表示出来。

我们只需要在一开始对装备以花费为关键字进行升序排序即可。并且为了不开结构体，本题可以使用冒泡排序。

然后依次加入装备，进行类似高斯消元的操作。

$$
\begin{bmatrix}
\mathbf z_{1_1} & \mathbf z_{1_2} & \mathbf z_{1_3} & \cdots\\
\mathbf z_{2_1} & \mathbf z_{2_2} & \mathbf z_{2_3} & \cdots\\
\vdots & \ddots & \ddots & \cdots\\
\mathbf z_{n_1} & \mathbf z_{n_2} & \mathbf z_{n_3} & \cdots
\end{bmatrix}
$$
（下文矩阵第 $ i$ 行第 $ j$ 列用 $ f_{i,j}$ 表示）

把每一行用上面的式子消掉，对于已经做过的第 $ i$ 行的式子保证了 $ f_{i,i}=1$ 因此对于第 $ j$ 个不为空的行 $ (j>i)$ 可以让 $ (1\le k< j) f_{j,k}$ 为 $ 0$ 。然后让整行同除 $ f_{j,j}$ ，但是没有必要消掉前面行的第 $ j$ 列。因为不需要解方程，并且该被表示出来的总是能被表示出来的。

如果第 $ j$ 行第 $ j$ 列是 $ x$ ，那么这一行就变成了

$$
\begin{bmatrix}
\cdots & \frac{f_{j,j}}{x} & \frac{f_{j,j+1}}{x} & \frac{f_{j,j+2}}{x} & \cdots
\end{bmatrix}
$$

其中 $ \frac{f_{j,j}}{x}=1$。

当 $ \forall j\in [1,m], f_{i,j}=0$ 时，则说明这一行可以被前面的向量表示出来，因此它是不需要的。由于排过序，我们自动地选择了能表示这组向量的最小花费。

然后通过判断每个装备是否被选，把答案统计一下就可以了。

时间复杂度 $ O(nm^2+n^2)$。

有个可能越界的神仙地方，LOJ过了，luoguRE了……

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define db double
using std::swap;
db f[505][505];
int c[505];
bool qaq[505];
int main()
{
    int n,m,sum=0,tot;
    scanf("%d%d",&n,&m);
    tot=n;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            scanf("%lf",&f[i][j]);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&c[i]);
        sum+=c[i];
    }

    for(int i=1;i<=n;++i)
        for(int j=i-1;j>=1;--j)
            if(c[j+1]<c[j])
            {
                swap(f[j+1],f[j]);
                swap(c[j+1],c[j]);
            }

    for(int i=1;i<=n;++i)
    {
        int cnt=0;
        qaq[i]=1;
        for(int j=1;j<i;++j)
        {
            if(!qaq[j])
                continue;
            if(cnt<m)
                ++cnt;
            db d=f[i][cnt];
            int flag=0;
            for(int k=cnt;k<=m;++k)
            {
                f[i][k]-=d*f[j][k];
                if(fabs(f[i][k])>1e-5)
                    flag=1;
            }
            if(!flag)
            {
                sum-=c[i];
                --tot;
                qaq[i]=0;
                break;
            }
        }
        if(!qaq[i])
            continue;
        cnt=0;
        while(fabs(f[i][cnt])<1e-5)
            ++cnt;
        db d=f[i][cnt];
        for(int j=cnt;j<=m;++j)
            f[i][j]/=d;
    }
    printf("%d %d\n",tot,sum);
    return 0;
}