如何优化我的dp编程解决方案以更快地完成算法任务

Question

现在，当我们有一台计算机时，我们需要为计算机供电n天。每天的商店都提供m个电池，每个电池只能使用一天。另外，当您当天购买k件商品时，需要支付k ^ 2的税。打印运行n天的最低成本

For example for 
5 5
100 1 1 1 1 
100 2 2 2 2 
100 3 3 3 3 
100 4 4 4 4
100 5 5 5 5 
Output will be 18

10 1 
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
Output will be 10000000010

我无法比检查所有可能性更快地完成此任务。您能指出我更好的解决方案吗？限制1 <= n * m <= 10 ^ 6价格可以从1到10 ^ 9。

Answer 1

您可以简单地为每一天排序元素（您将要首先选择每天的最低价格），然后将项目作为值+税项添加到优先级队列中（当税项计算为2 * j -1时， j是当日值得购买的第j个商品。这是起作用的原因，k ^ 2--（k + 1）^ 2。而且每天您都将移除第一个商品（目前可以购买的最好的电池）。

#include <iostream>
#include <utility>
#include <algorithm>
#include <queue>
#include <cmath>
#include <vector>

using namespace std;

int n, m;
vector <long long> pom;
int x;
priority_queue<long long> q;

long long score;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> x;
            pom.push_back(x);
        }
        sort(pom.begin(), pom.end());

        for(int j = 0; j < pom.size(); j++){
            pom[j] += 1 + 2 * j;
            q.push(-pom[j]);
        }
        pom.clear();
        score += q.top();
        q.pop();
    }

    cout << -score;


}

该解决方案的复杂度为O（n * m logm）