题解 P5858 【「SWTR-03」Golden Sword】
FjswYuzu
·
·
题解
$\ \ \ \ \ \ \ $考虑到要顺序放置，贡献与当前锅内的原料有关，所以我们考虑将这两个东西加入我们的 dp 式。
$\ \ \ \ \ \ \ $设 $dp_{i,j}$ 为放进 $i$ 原料，且当时正有 $j$ 个原料所得到的最大耐久度。有 dp 方程：
$$dp_{i,j}=\max \{dp_{i-1,k}+a_i \times j\}$$
$\ \ \ \ \ \ \ $其中$j-1 \leq k \leq \min \{m,j+s-1\}$。
```cpp
#include<bits/stdc++.h>
using namespace std;
long long n,m,s,a[5505],dp[5505][5505];
int main(){
scanf("%lld %lld %lld",&n,&m,&s);
for(long long i=1;i<=n;++i) scanf("%lld",&a[i]);
for(long long i=0;i<=n;++i) for(long long j=0;j<=m;++j) dp[i][j]=-1008600110086001;
dp[0][0]=0;
for(long long i=1;i<=n;++i)
{
for(long long j=m;j;--j)
{
for(long long k=min(m,j+s-1);k>=j-1;--k)
{
// i-1 k j*a;
dp[i][j]=max(dp[i][j],dp[i-1][k]+j*a[i]);
}
}
}
long long ans=-1008600110086001;
for(long long i=0;i<=m;++i) ans=max(ans,dp[n][i]);
printf("%lld",ans);
return 0;
}
```
$\ \ \ \ \ \ \ $因为这个代码实际上是 $O(nm^2)$ 的。实际因为数据过于水，得到 85。差评。
$\ \ \ \ \ \ \ $考虑到我们枚举 $j \times a_i$ 是一个定值。所以说我们的 dp 方程简化为：
$$dp_{i,j}=\max \{dp_{i-1,k}\}+a_i \times j$$
$\ \ \ \ \ \ \ $其中$j-1 \leq k \leq \min \{m,j+s-1\}$。
$\ \ \ \ \ \ \ $我们惊奇地发现，中间 $\max$ 的一坨是可以单调队列优化的！
$\ \ \ \ \ \ \ $~~（当然你也可以用线段树，我调爆了）~~
$\ \ \ \ \ \ \ $实际上这就是一道单调队列的板子题吧。。。
```cpp
#include<bits/stdc++.h>
using namespace std;
long long n,m,s,a[5505],dp[5505][5505],q[5505],pos[5505];
int main(){
scanf("%lld %lld %lld",&n,&m,&s);
for(long long i=1;i<=n;++i) scanf("%lld",&a[i]);
for(long long i=0;i<=n;++i) for(long long j=0;j<=m;++j) dp[i][j]=-1008600110086001;
dp[0][0]=0;
for(long long i=1;i<=n;++i)
{
int l=1,r=1;
q[l]=dp[i-1][m];
pos[l]=m;
for(long long j=m;j;--j)
{
while(pos[l]>j+s-1 && l<=r) ++l;
while(q[r]<dp[i-1][j-1] && l<=r) --r;
pos[++r]=j-1;
q[r]=dp[i-1][j-1];
dp[i][j]=q[l]+j*a[i];
}
}
long long ans=-1008600110086001;
for(long long i=0;i<=m;++i) ans=max(ans,dp[n][i]);
printf("%lld",ans);
return 0;
}
```