问题描述:

脸哥最近在玩一款神奇的游戏,这个游戏里有 $n $件装备,每件装备有$ m$ 个属性,用向量$z_i(a_j ,…..,a_m)$ 表示。每个装备需要花费 $ci$,现在脸哥想买一些装备,但是脸哥很穷,所以总是盘算着怎样才能花尽量少的钱买尽量多的装备。

如果脸哥买了 $z_{i1},…..z_{ip}$这$ p$ 件装备,那么对于任意待决定的 $z_h$,不存在 $b_1,….,b_p$ 使得 $b_1z_{i1} + … + b_pz_{ip} = z_h$($b$ 是实数),那么脸哥就会买 $z_h$,否则 $z_h$ 对脸哥就是无用的了,自然不必购买。脸哥想要在买下最多数量的装备的情况下花最少的钱,你能帮他算一下吗?

输入:

第一行两个数 $n$,$m$。接下来$ n $行,每行 $m$ 个数,其中第$ i $行描述装备$ i $的各项属性值。
接下来一行$ n $个数,其中$ c_i $表示购买第 $i $件装备的花费。

输出:

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

思路:

题目说简单一点就是你要在一组向量中,要求出最大的线性无关子集,也就是线性基。

线性基的求法就是把$n$个向量看成是$n*m$的系数矩阵,然后进行高斯消元,剩下的非零向量就是线性基,那么最多的装备数量就是线性基的大小。但是我们还要维护它的最小花费,这时我们就可以使用贪心的策略了,可以将价格排一个序,消元时尽可能用价格低的消去其他的,这样就可以了。

这个的证明也很有趣,因为线性基是是线性无关的,如果有一个价格更低的能被它们表示,那么我们可以放进去一个价格低的,取出一个价格高的。这样,价格高的一定能被新的线性基表示,所以我们可以使用这种贪心策略。

代码:

#include <bits/stdc++.h>
#define LB long double
#define eps 1e-6
#define MAXN 505
using namespace std;

int n, m, num, val, f[MAXN];

struct Weap {LB z[MAXN]; int val;} weap[MAXN];

bool CMP(Weap x, Weap y) {return x.val<y.val;}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) scanf("%llf", &weap[i].z[j]);
    for(int i=1; i<=n; i++) scanf("%d", &weap[i].val);

    sort(weap+1, weap+n+1, CMP);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            if(fabs(weap[i].z[j])<eps) continue;
            if(f[j]==0)
            {
                f[j]=i;
                num++; val+=weap[i].val;
                break;
            }
            else
            {
                LB rate=weap[i].z[j]/weap[f[j]].z[j];
                for(int k=j; k<=m; k++) weap[i].z[k]-=rate*weap[f[j]].z[k];
            }
        }
    printf("%d %d\n", num, val);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注