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

作者: wjyyy 分类: 线性代数,线性基,解题报告,贪心 发布时间: 2019-02-25 20:40

点击量:21

线性基思想入门题。

题目描述

脸哥最近在玩一款神奇的游戏,这个游戏里有 \(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;
}

说点什么

avatar
  Subscribe  
提醒
/* */