装备购买(BZOJ4004)高斯消元+ 贪心

电玩女神 2024-04-17 05:53 54阅读 0赞

脸哥最近在玩一款神奇的游戏，这个游戏里有 n 件装备，每件装备有 m 个属性，用向量z\[i\]=(ai,1,ai,2,…,ai,m) 表示，每个装备需要花费 ci

。

现在脸哥想买一些装备，但是脸哥很穷，所以总是盘算着怎样才能花尽量少的钱买尽量多的装备。

对于脸哥来说，如果一件装备的属性能用购买的其他装备组合出（也就是说脸哥可以利用手上的这些装备组合出这件装备的效果），那么这件装备就没有买的必要了。

严格的定义是，如果脸哥买了 z\[i1\],z\[i2\],…,z\[ip\]  
这 p 件装备，并且不存在实数 b1,b2,…,bp 使得z\[k\]=b1z\[i1\]+b2z\[i2\]+…+bpz\[ip\]，那么脸哥就会买z\[k\]，否则 z\[k\]

对脸哥就是无用的了，自然不必购买。

脸哥想要在买下最多数量的装备的情况下花最少的钱，你能帮他算一下吗？  
输入格式

第一行包含两个整数 n和m。

接下来 n 行，每行 m 个数，其中第 i 行描述装备 i 的各项属性值。

接下来一行 n 个数，其中第i个数表示购买第 i 件装备的花费ci

。  
输出格式

输出占一行，包含两个整数，第一个整数表示能够购买的最多装备数量，第二个整数表示在购买最多数量的装备的情况下的最小花费。  
数据范围

1≤n,m≤500  
,  
0≤ai,j≤1000

输入样例：

3 3  
1 2 3  
3 4 5  
2 3 4  
1 1 2

输出样例：

2 2

分析：  
参考博客： https://www.cnblogs.com/RogerDTZ/p/9215566.html  
此题，基本思路就是为高斯消元的基本思路。  
z\[k\]=b1z\[i1\]+b2z\[i2\]+…+bpz\[ip\]这就是线性相关的线性表示。  
故，一件装备如果不需要买，那么这件装备势必可以用其他装备进行线性表出。  
所以，就是求一个向量的最大无关组。  
这样可以得到最少要买多少个装备。那么，至少花费多少钱就需要用到一个简单的贪心。

这个题恶心的地方就是在于卡精度。需要long double。每次除法都都卡精度。恶心

#include"stdio.h"
    #include"string.h"
    #include"math.h"
    #include"algorithm"
    using namespace std;
    #define eps (long double)1e-8
    #define Bug printf("bug\n");
    typedef struct Node
    {
        long double weight[510];
        int price;
    }Node;
    
    Node node[510];
    int n,m;
    long double a[510][510];
    
    int cmp(Node a,Node b)
    {
        return a.price < b.price;
    }
    
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i = 1; i <= n; i ++)
           for(int j = 1; j <= m; j ++)
               scanf("%llf",&node[i].weight[j]);
        for(int i = 1; i <= n; i ++)
            scanf("%d",&node[i].price);
        sort(node + 1,node + 1 + n,cmp);
        int ans = 0; int price = 0;
    
        for(int i = 1; i <= n; i ++)
        {
            for(int j = 1; j <= m; j ++)
            {
                if(fabs(node[i].weight[j]) >= eps)
                {
                    if(fabs(a[j][j]) < eps)
                    {
                        for(int k = j; k <= m; k ++)
                            a[j][k] = node[i].weight[k];
                        ans ++; price += node[i].price;
                    }
                    for(int k = m; k >= j; k --)
                    {
                        node[i].weight[k] -= a[j][k] * (node[i].weight[j]/a[j][j]);
                    }
                }
            }
        }
        printf("%d %d\n",ans,price);
    }