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

Question

Now when we have a computer we need to power it, for n days. Each days shop offers m batteries which will last for only one day each. Additionaly when you are buying k items that day you need to pay tax which is k^2. Print the minimum cost to run your computer for n days

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)

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

How to optimize my solution to dp programming to algorithmic task faster

language-agnostic

algorithm

optimization

performance

dynamic-programming