题目链接:
https://www.luogu.com.cn/problem/P5858
题目大意:
小 E 打算铸剑,现在有 n 种原料,编号从 1 到 n,下标为 i 的原料坚固值为 ai, 按照 1 到 n 的顺序依次加入炼金炉,但是炼金炉只能容纳 w 个原料,每放入一个原料前可以取出不超过 s 个的原料,宝剑的耐久度为所有原料耐久度之和,而第 i 种原料的耐久度为放入这种原料时锅内的原料总数(包括正在放入的)* ai,求最大的耐久度。
思路:
原料是按照顺序放入的,同时放入的原料又有限制,可以想到构建一个二维 DP 数组 dp[i][j], i 表示当前放入第几个原料,j 表示当前炉中有几个原料,于是我们可以写出下面的代码。
for (LL i = 1; i <= n; i++) //当前是第几个原料
for (LL j = w; j >= 1; j--) //当前炉中有几个原料
for (LL k = j - 1; k <= min(w, j + s - 1); k++) //放入前可能剩下的原料
dp[i][j] = max(dp[i][j], dp[i - 1][k] + j * a[i]); //加入新的原料
上述代码的时间复杂度为 O(n * w * w),于是我们考虑优化,可以看到,最内层的 for 循环其实就是找到最大的耐久度后加入新原料,我们可以通过单调队列来实现。
代码:
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL INF = -1e16 + 10;
const int maxn = 5e3 + 10;
LL n, w, s, dp[maxn][maxn], ans, q[maxn], pos[maxn];
vector <LL> a(maxn);
int main(){
cin >> n >> w >> s;
for (LL i = 1; i <= n; i++)
scanf("%lld", &a[i]);
for (LL i = 0; i <= n; i++)
for (LL j = 0; j <= w; j++)
dp[i][j] = INF;
dp[0][0] = 0;
for (LL i = 1; i <= n; i++){
LL l = 1, r = 1;
q[l] = dp[i - 1][w];
pos[l] = w;
for (LL j = w; j >= 1; j--){
while (l <= r && pos[l] > j + s - 1) l++; //取出原料
while (l <= r && q[r] < dp[i - 1][j - 1]) r--; //构建单调递减的队列
pos[++r] = j - 1; //记录加入的原料的编号
q[r] = dp[i - 1][j - 1];
dp[i][j] = q[l] + j * a[i];
}
}
ans = INF;
for (LL i = 0; i <= w; i++)
ans = max(ans, dp[n][i]);
cout << ans << "\n";
return 0;
}