问题描述：
脸哥最近在玩一款神奇的游戏，这个游戏里有 $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$的系数矩阵，然后进行高斯消元，剩下的非零向量就是线性基，那么最多的装备数量就是线性基的大小。但是我们还要维护它的最小花费，这时我们就可以使用贪心的策略了，可以将价格排一个序，消元时尽可能用价格低的消去其他的，这样就可以了。
这个的证明也很有趣，因为线性基是是线性无关的，如果有一个价格更低的能被它们表示，那么我们可以放进去一个价格低的，取出一个价格高的。这样，价格高的一定能被新的线性基表示，所以我们可以使用这种贪心策略。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #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);
}
|