洛谷 P5858 「SWTR-03」Golden Sword

Description

制造一把金宝剑需要 $n$ 种原料，编号为 $1$ 到 $n$ ，编号为 $i$ 的原料的坚固值为 $a_i$ 。

炼金是很讲究放入原料的顺序的，因此小 E 必须按照 $1$ 到 $n$ 的顺序依次将这些原料放入炼金锅。

但是，炼金锅的容量非常有限，它最多只能容纳 $w$ 个原料。

所幸的是，每放入一个原料之前，小 E 可以从中取出一些原料，数量不能超过 $s$ 个。

我们定义第 $i$ 种原料的耐久度为：放入第 $i$ 种原料时锅内的原料总数（包括正在放入的原料） $×ai \times a_i$ ，则宝剑的耐久度为所有原料的耐久度之和。

小 E 当然想让他的宝剑的耐久度尽可能得大，这样他就可以带着它进行更多的战斗，请求出耐久度的最大值。

注：这里的“放入第 $i$ 种原料时锅内的原料总数包括正在放入锅中的原料，详细信息请见样例。

Input

第一行，三个整数 $n, w, s$ 。

第二行， $n$ 个整数 $a_1,a_2,\dots,a_n$ 。

Output

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

Solution

1.考虑dp做法。

1.定义

令dp[i][j]为：当正在放第 $i$ 种原料进锅里，锅里正好有 $j$ 种原料时的宝剑耐久度总和。

2.初始化

根据数据可得，要先将dp数组设一个很小的负数。

特别地，dp[0][0] = 0。

3.状态转移

由于在放原料进锅之前，可以取出小于等于 $s$ 的原料数量。所以 $j$ 最低可以从j-1转移而来（一个原料都不拿出去），最多可以从min(w, j+s-1)（拿出 $s$ 种原料或者锅的容量上限 $w$ ），即：

 for(int i=1; i<=n; i++)// 当前是第几个原料 for(int j=w; j>=1; j--)// 当前炉子中有几个原料 for(int k=j-1; k<=min(w, j+s-1); k++)// 放入当前可能剩下的原料 // 拿得最多在j+s-1的时候拿走s个 // 剩下j-1个，再放一个形成j个 // 或者不能超越炉子容量 dp[i][j] = max(dp[i][j], dp[i-1][k]+j*a[i]);

4.单调队列优化

以上算法时间复杂度为 $O(n^2w)$ ，时间只给500ms，显然超时。

不难发现，式子存在单调性质：

由于我们是从 dp[i][w] 往dp[i][1]更新答案，

如果dp[i-1][k] <= dp[i-1][j]且k>j时，dp[i-1][k]就可以被对答案更大贡献的dp[i-1][j]替代。

因为更大的 k 也意味着被弹出队列的可能性更大，而区间[j-1, min(w, j+s-1)]是整体往数值小的区间去移动。

用单调队列实现操作如下：

一个单调队列p维护k的取值区间，

一个单调队列维护dp[i-1][j-1]的最大值。

遍历每一个dp[i][j]，此时滑动窗口里的q[left]存放的即为dp[i-1][k]的最大值

如果队尾小于 dp[i-1][j-1] ，那么就将队尾弹出队列（因为），将dp[i-1][j-1]即当当前情况下的第二维最小的情况推入队列，；然后将队列里面一定不是最优解的情况全部从尾部删除。

计算到dp[i][j] $(i > 1, j > 1)$ 时，如果单调队列的队头dp[i-1][k]已经超过范围，即不符合 $k < = j + s - 1$ ，那么就将dp[i-1][k]弹出单调队列（从队头弹出）。

这样就实现了 $O (1)$ 转移。

Code

#include <bits/stdc++.h> typedef long long ll; #define itn int //ovo #define MOD  using namespace std; inline ll read() { 
    ll x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){ 
   if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){ 
   x=x*10+ch-48;ch=getchar();} return x*f; } ll n, w, s; ll a[5005]; ll dp[5005][5005]; // 记录下标，记录最大dp值 ll p[5005], q[5005]; void solve() { 
    n = read(), w = read(), s = read(); for(int i=1; i<=n; i++) { 
    a[i] = read(); } for(int i=0; i<=n; i++) { 
    for(int j=0; j<=w; j++) { 
    dp[i][j] = -0000000; } } dp[0][0] = 0; ll ans = -0000000; // 当前是第几个原料 for(int i=1; i<=n; i++) { 
    ll left = 1, right = 1; p[left] = w; q[right] = dp[i-1][w]; cout << "i = " << i << endl; // 当前炉子中有几个原料 for(int j=w; j>=1; j--) { 
    // 显然，left只会不断往右移 // p数组维护容量区间 // 在p数组里找到上一轮最大的容量值 while(p[left]>j+s-1 && left<=right) left++; // 在q数组里找到上一轮最大的dp值 while(q[right]<dp[i-1][j-1] && left<=right) right--; right++; p[right] = j-1; // p数组放进最小容量j-1 q[right] = dp[i-1][j-1]; // q数组放进dp[i-1][j-1] // 容量区间内最大容量 dp[i][j] = q[left] + j*a[i]; } } for(int i=1; i<=w; i++) ans = max(ans, dp[n][i]); cout << ans; } int main(void) { 
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); // come on solve(); return 0; }

今天的文章洛谷 P5858 「SWTR-03」Golden Sword分享到此就结束了，感谢您的阅读。