题解 P5858 【「SWTR-03」Golden Sword】
zumgze
2019-12-28 20:09:25
$20200214markdown$
~~可能是数据的问题，此方法总体上跑得比单调队列快。~~
我们可以叫它 **及时终止的动态规划。**
这个算法在不开优化的情况下大约会运行400ms。
---
我们首先定义$dp[i][j]$为放入第 *i* 个原料后锅内的原料有 *j* 个的时候的耐久度之和，$a[i]$为依次放入的原料。
当处于$dp[i][j]$的状态的时候，向锅里加入原料$a[i+1]$，想想会发生什么？
$j$个原料再放入一个原料是$j+1$个原料，**由于可以取出0~s个原料，所以锅里剩下的原料数的范围是$[j+1-s,j+1]$。**
之后再考虑锅的容量，最少$0$个原料，最多$w$个原料,**所以范围就变成了$[max(0,j+1-s),min(w,j+1)]$。**
所以我们可以用$dp[i][j]$来更新$dp[i+1][k]$。
再考虑初始条件，当还没有开始放原料的时候，耐久度必然是0。即$dp[0][0]=0$。
---
#### 然而单纯这样是过不了的，所以我们还要做出两点优化。
①由于（这里是单独拿出第一维来说）$dp[i]$的值只用来更新$dp[i+1]$，此时$dp[i-1]$及之前的都已经没有用的，所以也就没有储存的必要。所以我们只需要存储$dp[i]$和$dp[i+1]$，从而降低了空间复杂度。
② **考虑及时终止。**
当用$dp[i][j]$来更新$dp[i+1][k]$的时候，观察式子$dp[i+1][k]=max(dp[i+1][k],dp[i][j]+k*a[i])$。
---
#### 发现增量只与当前锅内的原料数和刚放进去的原料有关。
当用$dp[i][j]$来更新$dp[i+1][k]$的时候，我们顺序枚举$j$，倒序枚举$k$。
若出现$dp[i][j]+k*a[i] \leq dp[i+1][k]$，那么就不需要枚举$k$了，因为这说明在枚举$dp[i][j]$之前，已经出现过一个更大的值将$dp[i+1][k]$更新过了，从而对于$dp[i+1][k-1]$及之后的每一个，$dp[i][j]$都不可能更大。
代码如下：
```cpp
#include<bits/stdc++.h>//算法复杂度O(n*w*w) AC 100points
using namespace std;
long long a[10000],dp[10000];
inline long long read()//读入优化不多说
{
long long x=0;
bool f=false;
char ch=getchar();
while(ch<'0'||ch>'9')
{
f|=(ch=='-');
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
if(f)return -x;
else return x;
}
int main()
{
long long n,w,s;
n=read();
w=read();
s=read();
for(long long i=0;i<n;i++)a[i]=read();
for(long long j=1;j<=w;j++)dp[j]=-9999999999999999ll;//初值负无穷
dp[1]=a[0];//当放入第1个原料时，锅中的原料数只能为1，这就是dp初始条件
for(long long i=1;i<n;i++)
{
long long help[10000];//此时dp[j]相当于dp[i][j]
//此时help[j]相当于dp[i+1][j]
for(long long j=1;j<=w;j++)help[j]=-9999999999999999ll;//初值负无穷
for(long long j=1;j<=w&&j<=i;j++)//j<=i是放入第i个原料后最多可以使锅里有i个原料
{//注意这里枚举j一定是正序的
for(long long k=min(w,j+1);k>=1&&k>=j-s+1;k--)//注意这里枚举k一定是倒序的
if(help[k]<dp[j]+k*a[i])help[k]=dp[j]+k*a[i];
else break;//如果help[k]>=dp[j]+k*a[i]，说明dp[j]这个解没有之前的解优
}
for(long long j=1;j<=w;j++)dp[j]=help[j];//将help数组拷贝到dp数组，为下一个循环做准备
}
long long ans=-9999999999999999ll;//初值负无穷
for(long long i=1;i<=w;i++)ans=max(ans,dp[i]);//放入最后1个原料后，枚举此时锅中的原料数，求最大值
printf("%lld",ans);
return 0;
}
```