Description
脸哥最近在玩一款神奇的游戏, 这个游戏里有 n 件装备, 每件装备有 m 个属性, 用向量 zi(aj ,.....,am) 表示
(1 <= i <= n; 1 <= j <= m), 每个装备需要花费 ci, 现在脸哥想买一些装备, 但是脸哥很穷, 所以总是盘算着
怎样才能花尽量少的钱买尽量多的装备. 对于脸哥来说, 如果一件装备的属性能用购买的其他装备组合出 (也就是
说脸哥可以利用手上的这些装备组合出这件装备的效果), 那么这件装备就没有买的必要了. 严格的定义是, 如果
脸哥买了 zi1,.....zip 这 p 件装备, 那么对于任意待决定的 zh, 不存在 b1,....,bp 使得 b1zi1 + ... + bpzi
p = 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 了. 脸哥想要在买下最多数量的装备的情况下花最少的钱, 你能帮他算一下吗?
Input
第一行两个数 n;m. 接下来 n 行, 每行 m 个数, 其中第 i 行描述装备 i 的各项属性值. 接下来一行 n 个数,
其中 ci 表示购买第 i 件装备的花费.
Output
一行两个数, 第一个数表示能够购买的最多装备数量, 第二个数表示在购买最多数量的装备的情况下的最小花费
- Sample Input
- 3 3
- 1 2 3
- 3 4 5
- 2 3 4
- 1 1 2
- Sample Output
- 2 2
- Solution
还是有关那个带权线性基的问题, 但是我还未膜拜拟阵证明, 所以就先写着吧.
我们发现, 这个新物品购买与否的判定机制, 是看用已购买的物品能否线性表示出新物品. 这不就是线性基的那一套插入, 判定能否线性表示的做法吗?
再考虑到那个贪心的方法 -- 我们要使选中的物品价值尽可能小, 那么依照套路我们按物品价值从小到大依次考虑, 尝试加入线性基: 能, 那就买; 中途消成 0, 就说明它可以被线性表示, 不买.
这题的实现不再能直接套用异或线性基的写法了, 而是要用实数来模拟线性基. 记线性基的向量为 \(b_1,b_2,...,b_m\), 其实每一个 \(b_i\) 类比于异或线性基中的每一个数, 只不过异或线性基还把向量状压了. 线性基用矩阵表示就长这样:
\[ \begin{bmatrix} b_{m,1}&b_{m,2} &b_{m,3} &... &b_{m,m}\...&...&...&...&...\b_{3,1}&b_{3,2} &b_{3,3} &... &b_{3,m}\b_{2,1}&b_{2,2} &b_{2,3} &... &b_{2,m}\b_{1,1}&b_{1,2} &b_{1,3} &... &b_{1,m}\\end{bmatrix} \]
? 尝试加入一个向量 \(a=[a_1,a_2,...,a_m]\) 时, 我们从 \(b_m\) 开始, 一行一行地循环到 \(b_1\). 考虑 \(b_i\) 时, 如果 \(a_i=0\),continue; 如果 \(b_{i,i}=0\), 我们把整个 \(b_i\) 赋值为 \(a\); 如果 \(b_{i,i}\ne0\), 我们用 \(b_i\) 消去 \(a_{i,i}\), 继续往下走. 类比异或线性基的插入方法, 就能很好地理解普通线性基的插入方法.
由于 BZOJ 新加了三组毒瘤数据, 因此实数要用 long double 保证精度.
- Code
- #include <cstdio>
- #include <algorithm>
- #include <cmath>
- using namespace std;
- typedef long double ld;
- const int N=505;
- const ld EPS=1e-8;
- int n,m;
- ld lb[N][N];
- struct Equip{
- ld a[N];
- int cost;
- }s[N];
- int use,sum;
- inline bool cmp(const Equip &x,const Equip &y){return x.cost<y.cost;}
- int main(){
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++)
- for(int j=1,x;j<=m;j++) scanf("%llf",&s[i].a[j]);
- for(int i=1;i<=n;i++) scanf("%d",&s[i].cost);
- sort(s+1,s+1+n,cmp);
- for(int x=1;x<=n;x++)
- for(int i=1;i<=m;i++)
- if(fabs(s[x].a[i])>=EPS){
- if(fabs(lb[i][i])<EPS){
- for(int j=i;j<=m;j++) lb[i][j]=s[x].a[j];
- use++;
- sum+=s[x].cost;
- break;
- }
- for(int j=m;j>=i;j--)
- s[x].a[j]-=lb[i][j]*(s[x].a[i]/lb[i][i]);
- }
- printf("%d %d\n",use,sum);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2655159.html