原题连接
更好的阅读体验

题目描述

脸哥最近在玩一款神奇的游戏，这个游戏里有 n 件装备，每件装备有 m 个属性，用向量$z[i]=(a_{i,1},a_{i,2} ,..,a_{i,m})$ 表示，每个装备需要花费 $c_i$。

现在脸哥想买一些装备，但是脸哥很穷，所以总是盘算着怎样才能花尽量少的钱买尽量多的装备。

对于脸哥来说，如果一件装备的属性能用购买的其他装备组合出（也就是说脸哥可以利用手上的这些装备组合出这件装备的效果），那么这件装备就没有买的必要了。

严格的定义是，如果脸哥买了 $z[i_1],z[i_2],…,z[i_p]$这 p 件装备，并且不存在实数 $b_1,b_2,…,b_p$ 使得$z[k]=b_1z[i_1]+b_2z[i_2]+…+b_pz[i_p]$，那么脸哥就会买$z[k]$，否则 $z[k]$对脸哥就是无用的了，自然不必购买。

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

输入格式
第一行包含两个整数 n和m。

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

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

输出格式
输出占一行，包含两个整数，第一个整数表示能够购买的最多装备数量，第二个整数表示在购买最多数量的装备的情况下的最小花费。

数据范围
$1≤n,m≤500$
$0≤ai,j≤1000$

样例

输入样例：
3 3
1 2 3
3 4 5
2 3 4
1 1 2
输出样例：
2 2

高斯消元+贪心

这道题目总的来说,就是转换思想,首先我们可以把$N$件装备,看作N个向量,然后根据题意,我们最后选出来的装备,肯定都是线性无关的.什么是线性无关,大学的大佬们都知道,就是这些向量是无法根据其他变量组合出来.也就是题目的条件.

我们把$a_{i,j}$看作系数矩阵,把每个装备$z_i$看作行变量即可.

然后转化过后,我们的目标是什么,那那就是求出矩阵的秩,也就是最多的装备数量,然后题目要求我们的氪金最少,那么我们自然可以利用到贪心,对于每个主元$x_i$而言,在前面$i-1$列位0,第$i$列不为空的行变量中,选择价格最低的一个,去消去其他行的系数.

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define N 510
long double a[N][N],eps=1e-8;
double temp;
int c[N],n,m,dim,now,ans,i,j;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%lf",&temp);
            a[i][j]=temp;
        }
    for(int i=1;i<=n;i++)
    {
        scanf("%lf",&temp);
        c[i]=temp;
    }
    dim=0;
    for(int i=1;i<=m;i++)
    {
        now=0;
        for(int j=dim+1;j<=n;j++)
            if (fabs(a[j][i])>eps && (now==0 || c[j]<c[now]))
            {
                now=j;
                continue;
            }
        if (now==0)
            continue;
        dim++;
        ans+=c[now];
        for(int j=1;j<=m;j++)
            swap(a[now][j],a[dim][j]);
        swap(c[now],c[dim]);
        for(int j=1;j<=n;j++)
            if (dim!=j && fabs(a[j][i])>eps)
            {
                long double rate=a[j][i]/a[dim][i];
                for(int k=i;k<=m;k++)
                    a[j][k]-=a[dim][k]*rate;
            }
    }
    cout<<dim<<" "<<ans<<endl;
    return 0;
}