线性基)"/>
BZOJ 4004 装备购买(贪心+线性基)
Description
脸哥最近在玩一款神奇的游戏,这个游戏里有 n 件装备,每件装备有
Input
第一行两个数 n;m 。接下来 n 行,每行
Output
一行两个数,第一个数表示能够购买的最多装备数量,第二个数表示在购买最多数量的装备的情况下的最小花费
Sample Input
3 3
1 2 3
3 4 5
2 3 4
1 1 2
Sample Output
2 2
Solution
把所有装备按价值从小到大排序后找线性基即可,贪心证明需用到拟阵
Code
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int>P;
const int INF=0x3f3f3f3f,maxn=505;
#define eps 1e-5
int sign(ld x)
{if(fabs(x)<eps)return 0;if(x>eps)return 1;return -1;
}
struct node
{ld x[maxn];int c;bool operator<(const node&b)const{return c<b.c;}
}a[maxn];
int n,m,base[maxn];
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%llf",&a[i].x[j]);for(int i=1;i<=n;i++)scanf("%d",&a[i].c);sort(a+1,a+n+1);int num=0,cost=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(sign(a[i].x[j])){if(!base[j]){base[j]=i,num++,cost+=a[i].c;break;}else{ld temp=a[i].x[j]/a[base[j]].x[j];for(int k=j;k<=m;k++)a[i].x[k]-=temp*a[base[j]].x[k];}}printf("%d %d\n",num,cost);return 0;
}
更多推荐
BZOJ 4004 装备购买(贪心+线性基)
发布评论