虽然不知道为什么讲到了线性基
不过首先建议如果没有学过线性基,出门左转
会得到更好的阅读体验
算法
实数的线性基+高斯消元+贪心
口胡一下思路
根据线性基的值域与原数组的值域相同
不断向加入值较小的基
再用高斯消元的思想(加减消元)将后面加减一下
仿佛这么一看就是道裸题?!
C++ 代码
#include<bits/stdc++.h>
#define re return
#define inc(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
template<typename T>inline void rd(T&x)
{
char c;bool f=0;
while((c=getchar())<'0'||c>'9')if(c=='-')f=1;
x=c^48;
while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);
if(f)x=-x;
}
typedef double D;
D EPS=1e-4;
const int maxn=505;
int p[maxn];
int cost[maxn],n,m,sum,ans;
inline D Fabs(D x)
{
re x>0?x:-x;
}
struct node
{
D x[maxn];
int cost;
inline bool operator<(node c)const
{
re cost<c.cost;
}
}a[maxn];
int main()
{
freopen("in.txt","r",stdin);
rd(n),rd(m);
inc(i,1,n)inc(j,1,m)
rd(a[i].x[j]);
inc(i,1,n)
rd(a[i].cost);
sort(a+1,a+n+1);//贪心
//值域相等情况下肯定要用花费小的
inc(i,1,n)
inc(j,1,m)
if(Fabs(a[i].x[j])>EPS)
{
if(!p[j])//加入基
{
p[j]=i;
++sum;
ans+=a[i].cost;
break;
}
D t=a[i].x[j]/a[p[j]].x[j];//消元
inc(k,j,m)
a[i].x[k]-=a[p[j]].x[k]*t;
}
printf("%d %d",sum,ans);
re 0;
}
传说
直接上高斯消元+膜质数也是阔以的
666