链接：https://ac.nowcoder.com/acm/problem/20146
来源：牛客网
题目描述
脸哥最近在玩一款神奇的游戏，这个游戏里有 n 件装备，每件装备有 m 个属性，用向量zi(aj ,.....,am) 表示 (1 ≤ i ≤ n; 1 ≤ j ≤ m)，每个装备需要花费 ci，现在脸哥想买一些装备，但是脸哥很穷，所以总是盘算着怎样才能花尽量少的钱买尽量多的装备。
对于脸哥来说，如果一件装备的属性能用购买的其他装备组合出（也就是说脸哥可以利用手上的这些装备组合出这件装备的效果），那么这件装备就没有买的必要了。
严格的定义是，如果脸哥买了 zi1,.....zip这 p 件装备，那么对于任意待决定的 zh，不存在 b1,....,bp 使得 b1zi1 + ... + bpzip = zh（b 是实数），那么脸哥就会买 zh，否则 zh 对脸哥就是无用的了，自然不必购买。
举个例子,z1 =(1; 2; 3);z2 =(3; 4; 5);zh =(2; 3; 4)，b1 =1/2，b2 =1/2，就有 b1z1 + b2z2 = zh，那么如果脸哥买了 z1 和 z2 就不会再买 zh 了。脸哥想要在买下最多数量的装备的情况下花最少的钱，你能帮他算一下吗？
输入描述:
第一行两个数 n;m。
接下来 n 行，每行 m 个数，其中第 i 行描述装备 i 的各项属性值。
接下来一行 n 个数，其中 ci 表示购买第 i 件装备的花费。
输出描述:
一行两个数，第一个数表示能够购买的最多装备数量 第二个数表示在购买最多数量的装备的情况下的最小花费
示例1
输入
3 3 1 2 3 3 4 5 2 3 4 1 1 2
输出
2 2
我们遇见的普通线性基（如模板题），都是在有关2进制与其异或和上用的
而这里用的是实数的线性基，在学实数的线性基之前，必须知道高斯消元的原理（因为我学线性基的时候没学高斯消元！！！）
那么我先讲一下为什么用高斯消元。
我们可以看到，如果物品aj可以用a1....aj-1组合而出的话，我们可以通过公式得到
k1*a1.x1+k2*a2.x1+k3*a3.x1+...+kj-1*aj-1.x1=aj.x1
k1*a1.x2+k2*a2.x2+k3*a3.x2+...+kj-1*aj-1.x2=aj.x2
......
k1*a1.xm+k2*a2.xm+k3.a3.xm+...+kj-1*aj-1.xm=aj.xm 我们就是要求出是否有这样的一组k使得上述等式成立
至于求解，我们可以用高斯消元。
但是由于这样做太过于麻烦，所以我们要结合线性基
假如我们将每个物品的属性看作向量，那么，我们要求的就是其中的一组基（如果一个物品可以通过其他的物品组合而成，那么它就不能是基的一部分）
我们上面的等式转化一下变成下面的
a1.x1,a1.x2,a1.x3...a1.xm ........1
a2.x1,a2.x2,a2.x3...a2.xm ........2
a3.x1,a3.x2,a3.x3...a3.xm ........3
...
aj.x1,aj.x2,aj.x3...aj.xm ........4 我们如果用高斯消元，用第一行的x1消去下面所有行的x1
然后用第二行剩下的x2（如果x2没有的话可以换一下行）,然后把剩下的行的x2消去
.....
如果消到最后，剩下的j所有项为0，那么aj就可以不选了。
多么愉快的是用高斯消元就行了！
这里就不讲高斯消元了
如果在消过元后有一个位置不是0，那么它就可以作为第i位的基（可以这么说吗？）
贪心。先按照价值从小到大排序
pos[j]代表着 第 j 项的 基底 在 第 i 个式子里面
如果我们找到了一个基底
我们就break掉
下个方程碰到这个基底，把他后面的所有的都模上（减去）含有基底的那个方程
也就是消元的思想
此外，这道题还可能卡精度（不过我没卡），可能要再模上一个大质数取逆元，在整数区域内求解
#include<bits/stdc++.h>
using namespace std;
struct node{
double val[555];
int cost;
};
bool cmp(const node &a,const node &b)
{
return a.cost<b.cost;
}
node p[555];
int pos[555];
double eps=1e-5;
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
scanf("%lf",&p[i].val[j]);
}
}
for(int i=0;i<n;i++)
{
scanf("%d",&p[i].cost);
}
sort(p,p+n,cmp);
memset(pos,-1,sizeof(pos));
int num=0,f=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(fabs(p[i].val[j])<=eps)
continue;
if(pos[j]==-1)
{
pos[j]=i;
num++;
f+=p[i].cost;
break;
}
else
{
double xs=p[i].val[j]/p[pos[j]].val[j];
for(int k=j;k<m;k++)
{
p[i].val[k]-=p[pos[j]].val[k]*xs;
}
}
}
}
printf("%d %d\n",num,f);
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
ll val[555];
ll cost;
};
ll mod=1e9+7;
ll qpow(ll a,ll n)
{
ll ans=1;
while(n)
{
if(n&1)
ans=ans*a%mod;
a=a*a%mod;
n>>=1;
}
return ans;
}
bool cmp(const node &a,const node &b)
{
return a.cost<b.cost;
}
node p[555];
ll pos[555];
double eps=1e-5;
int main()
{
ll n,m;
scanf("%lld%lld",&n,&m);
for(ll i=0;i<n;i++)
{
for(ll j=0;j<m;j++)
{
scanf("%lld",&p[i].val[j]);
}
}
for(ll i=0;i<n;i++)
{
scanf("%lld",&p[i].cost);
}
sort(p,p+n,cmp);
memset(pos,-1,sizeof(pos));
ll num=0,f=0;
for(ll i=0;i<n;i++)
{
for(ll j=0;j<m;j++)
{
if(fabs(p[i].val[j])<=eps)
continue;
if(pos[j]==-1)
{
pos[j]=i;
num++;
f+=p[i].cost;
break;
}
else
{
ll xs=p[i].val[j]*qpow(p[pos[j]].val[j],mod-2)%mod;
for(ll k=j;k<m;k++)
{
p[i].val[k]=(p[i].val[k]-p[pos[j]].val[k]*xs)%mod;
}
}
}
}
printf("%lld %lld\n",num,f);
}
京公网安备 11010502036488号