自动搬运

查看原文

来自洛谷，原作者为

	FjswYuzu Rainybunny狂热粉丝!111111 | Last Goodbye

搬运于2025-08-24 22:15:01，当前版本为作者最后更新于2019-12-29 08:30:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\ \ \ \ \ \ \$一道套路 dp 题，做法应该是显然，难度还不如 T3。

$\ \ \ \ \ \ \$考虑到要顺序放置，贡献与当前锅内的原料有关，所以我们考虑将这两个东西加入我们的 dp 式。

$\ \ \ \ \ \ \$设 $dp_{i,j}$ 为放进 $i$ 原料，且当时正有 $j$ 个原料所得到的最大耐久度。有 dp 方程：

$\ \ \ \ \ \ \$其中$j-1 \leq k \leq \min \{m,j+s-1\}$。

#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 方程简化为：

$\ \ \ \ \ \ \$其中$j-1 \leq k \leq \min \{m,j+s-1\}$。

$\ \ \ \ \ \ \$我们惊奇地发现，中间 $\max$ 的一坨是可以单调队列优化的！

$\ \ \ \ \ \ \$（当然你也可以用线段树，我调爆了）

$\ \ \ \ \ \ \$实际上这就是一道单调队列的板子题吧。。。

#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;
}