提问人：Jasqier346 提问时间：1/25/2020 更新时间：1/26/2020 访问量：74
如何更快地优化我的 dp 编程解决方案以完成算法任务
How to optimize my solution to dp programming to algorithmic task faster
问：
现在，当我们有一台计算机时，我们需要为它供电，持续 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。
答：
0赞
Jakub Swistak
1/26/2020
#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）
上一个：快速饱和整数转换？
评论