P5858 「SWTR-03」Golden Sword

题目背景

小E不幸在一场战斗中失去了他的金宝剑。

题目描述

制造一把金宝剑需要n种原料，编号为1到n，编号为i 的原料的坚固值为ai​。炼金是很讲究放入原料的顺序的，因此小E必须按照1到n的顺序依次将这些原料放入炼金锅。但是，炼金锅的容量非常有限，它最多只能容纳w个原料。所幸的是，每放入一个原料之前，小E可以从中取出一些原料，数量不能超过s个。我们定义第 i 种原料的耐久度为：放入第i种原料时锅内的原料总数*ai​，则宝剑的耐久度为所有原料的耐久度之和。小E当然想让他的宝剑的耐久度尽可能得大，这样他就可以带着它进行更多的战斗，请求出耐久度的最大值。

输入格式

第一行，三个整数 n,w,sn,w,sn,w,s。第二行，nnn 个整数 a1,a2,…,ana_1,a_2,\\dots,a_na1​,a2​,…,an​。

输出格式

一行一个整数，表示耐久度的最大值。

输入输出样例

输入

5 3 31 3 2 4 5

输出

40

题解

读完题，我们可以想到：1. 已经放入锅中的材料没有本质上的区别，对后面放入材料的贡献都为1。2. 加入新物品后，锅中材料数为j，可在材料数为j-1直接加入，或取出s个材料。故此，定义f[i,j]表示，放到第i个物品，箱子里有j个元素的最大价值和。状态转移方程：

f[i,j]=max⁡k=1→max(1,j−s)f[i−1][j−1]+a[i]∗k\\max\\limits_{k=1\\rightarrow max(1,j-s)} f[i-1][j-1]+a[i]*kk=1→max(1,j−s)max​f[i−1][j−1]+a[i]∗k( i→\\rightarrow→n,j→\\rightarrow→ min(m+1,i))。

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int n, m, s;int a[5005];long long f[5005][5005];int main() {long long ans = -0x3f3f3f3f3f3f;scanf(\"%d %d %d\", &n, &m, &s);for(int i = 1; i <= n; i++) {scanf(\"%d\", &a[i]);}memset(f, -0x3f, sizeof(f));f[0][0] = 0;for(int i = 1; i <= n; i ++) {for(int j = 1; j <= m + 1 && j <= i; j ++) {for(int k = j; k >= 1 && k >= j - s; k --) {if (f[i][k] <= f[i - 1][j - 1] + a[i] * k) {f[i][k] = f[i - 1][j - 1] + a[i] * k;}}}}for (int i = 1; i <= m; ++ i) {ans = max(ans, f[i]);}printf(\"%lld\", ans);}

然而时间复杂度为O(n3)，空间复杂度为O(n2)时间复杂度可由单调队列实现（但我似乎不会）
而空间复杂度可用滚动数组
滚动数组

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int n, m, s;int a[5005];long long f[2][5005];int main() {long long ans = -0x3f3f3f3f3f3f;scanf(\"%d %d %d\", &n, &m, &s);for(int i = 1; i <= n; i++) {scanf(\"%d\", &a[i]);}memset(f, -0x3f, sizeof(f));f[0][0] = 0;for(int i = 1; i <= n; i ++) {for(int j = 1; j <= m + 1 && j <= i; j ++) {for(int k = j; k >= 1 && k >= j - s; k --) {if (f[i & 1][k] <= f[(i - 1) & 1][j - 1] + a[i] * k) {f[i & 1][k] = f[(i - 1) & 1][j - 1] + a[i] * k;}}}}for (int i = 1; i <= m; ++ i) {ans = max(ans, f[n & 1][i]);}printf(\"%lld\", ans);}

单调队列

#include <cstdio>#include <algorithm>using namespace std;long long q[5555], n, w, s, a[5555], dp[2][5555], row = 1, ans = -1e15;int main(){scanf(\"%lld%lld%lld\", &n, &w, &s);for (int i = 1; i <= n; i++) scanf(\"%lld\", a + i);for (int i = 0; i <= 1; i++)for (int j = 0; j <= w; j++)dp[i][j] = -1e15;dp[0][0] = 0;for (int i = 1; i <= n; i++){for (int j = 0; j <= w; j++)dp[row][j] = -1e15;int h = 1, t = 1;q[h] = w;for (int j = w; j >= 1; j--){while (h <= t && q[h] > min(w, j + s - 1)) h++;while (h <= t && dp[row ^ 1][q[t]] < dp[row ^ 1][j - 1]) t--;//单点队列。q[++t] = j - 1;dp[row][j] = dp[row ^ 1][q[h]] + j * a[i];}row ^= 1;//变成另外一行}for (int i = 0; i <= w; i++)ans = max(ans, dp[n & 1][i]);//n奇偶不同最后一行的位置就不同。printf(\"%lld\\n\", ans);}————————————————版权声明：本文为CSDN博主「煜明」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/weixin_45646006/article/details/105314103

后面的代码是直接复制过来的，希望大家不要嘲讽介意
我只是过来提个思路罢了