题解
容易发现要买最多的装备数量就是 $n$ 个向量表出的线性空间的维数。
所以可以将 $n$ 个长度为 $m$ 的向量看成一个 $n\times m$ 的矩阵,进行高斯消元求出该矩阵的秩。
而要求价格最小,考虑贪心,消元到前 $i-1$ 列为 $0$ ,第 $i$ 列不为 $0$ 的行向量时,选择 $c_i$ 最小的向量。
证明如下:
对于价格最低的行向量 $z_k$ ,设其不在价格最低的选取方案 $z_1,z_2,\dots,z_p$ 中,
则 $z_k = b_1z_1+b_2z_2+\dots+b_pz_p$ ,必然存在 $b_i\ne 0$ ,
故 $z_i = (z_k - \sum\limits_{j\ne i} b_jz_j) / b_i$ 可由 $z_k,z_j(j\ne i)$ 表出,
又若 $z_k$ 可被 $z_j(j\ne i)$ 表出,那么这与 $z_1,z_2,\dots,z_p$ 为线性空间的基矛盾,
故 $z_k,z_j(j\ne i)$ 为线性空间的另一个基,且价格比原方案更低,矛盾,
故必然选择 $z_k$ 。
接着,假设消元过程中,当前选取了 $l-1$ 个前 $l-1$ 列有且仅有一列不为 $0$ 的向量,且满足贪心策略,
那么,对于前 $l-1$ 列为 $0$ ,第 $i$ 列不为 $0$ 的向量,则不能仅通过选取的 $l-1$ 个向量表出,
若不选取当前价格最低的向量,则仿照上面的证明方法也可以得到矛盾,
故贪心策略正确。
最后是精度的问题,eps=1e-4
貌似可以用 double
,再小就得开 long double
。
Code
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 505;
const long double eps = 1e-8;
inline void read(int &x)
{
int sgn = 1; x = 0;
char ch = getchar();
while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if(ch == '-') sgn = -1, ch = getchar();
while(ch >= '0' && ch <= '9') x = (x << 1) + (x << 3), x += (ch ^ '0'), ch = getchar();
x *= sgn;
}
int n, m, c[N];
long double a[N][N];
int main()
{
read(n); read(m);
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= m; j ++ ) scanf("%Lf", &a[i][j]);
for(int i = 1; i <= n; i ++ ) read(c[i]);
int dim = 0, res = 0;
for(int i = 1; i <= m; i ++ )
{
int now = 0;
for(int j = dim + 1; j <= n; j ++ )
if(fabs(a[j][i]) > eps && (now == 0 || c[j] < c[now]))
now = j;
if(now == 0) continue;
dim ++ ; res += c[now];
swap(c[dim], c[now]);
for(int j = 1; j <= m; j ++ ) swap(a[dim][j], a[now][j]);
for(int j = 1; j <= n; j ++ )
{
if(dim == j || fabs(a[j][i]) <= eps) continue;
long double rate = a[j][i] / a[i][i];
for(int k = i; k <= m; k ++ ) a[j][k] -= a[i][k] * rate;
}
}
printf("%d %d\n", dim, res);
return 0;
}