[JLOI2015]装备购买 (高斯消元)
2024-10-08 11:45:03
[JLOI2015]装备购买
$ solution: $
首先这道题的题面已经非常清晰的告诉我们这就是线性空间高斯消元的一道题(可以用某些装备来表示另一件装备,这已经不能再明显了),只是这道题要求我们求出花费最小的方案,这个我们可以直接贪心,如果有多个装备可以匹配某一个属性,那么我们选价值最小的那一个(这个可以用线性空间的定义证明),价值大的尽量往后再选(选到最后剩下一些价格大的不买即可)
$ code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define inf 0x7fffffff
#define rg register int
using namespace std;
const db cha=1e-4;
struct su{
db a[505];
int v;
inline bool operator <(su y){return v<y.v;}
}g[505];
int n,m,tot,ans;
int b[505];
inline int qr(){
char ch;
while((ch=getchar())<'0'||ch>'9');
int res=ch^48;
while((ch=getchar())>='0'&&ch<='9')
res=res*10+(ch^48);
return res;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
n=qr(); m=qr();
for(rg i=1;i<=n;++i)
for(rg j=1;j<=m;++j)
g[i].a[j]=qr();
for(rg i=1;i<=n;++i)
g[i].v=qr();
sort(g+1,g+n+1);
for(rg i=1;i<=n;++i){
for(rg j=1;j<=m;++j){
if(fabs(g[i].a[j])>cha){
if(!b[j]){
b[j]=i;++tot;
ans+=g[i].v;
break;
}else{
db d=g[i].a[j]/g[b[j]].a[j];
for(rg k=j;k<=m;++k)
g[i].a[k]-=g[b[j]].a[k]*d;
}
}
}
}printf("%d %d\n",tot,ans);
return 0;
}
最新文章
- UnrealScript语言基础
- ubuntu14.04 python3.*连接mysql
- require.js笔记
- linux中send函数MSG_NOSIGNAL异常消息
- Flume使用小结
- node.js在windows环境下的安装
- Java 7 jstat &ndash; JVM Statistics Monitoring Tool【翻译】
- MTK6589下传感器框架结构和代码分析以及传感器的参数指标
- To add private variable to this Javascript literal object
- scope的参数范围
- 关于web测试收集
- mysql中不等于过滤null的问题
- MIT-线性代数笔记(1-6)
- Kubernetes之RBAC
- talend工具中往oracle插数据报ORA-01461: can bind a LONG value only for insert into a LONG colum
- 实现一个简易版的SpringMvc框架
- hdu3635
- php的语句
- 八皇后问题C语言解法
- QtWidgets Module&#39;s Classes