自动搬运

查看原文

来自洛谷，原作者为

	dead_X Still we rise

搬运于2025-08-24 22:26:54，当前版本为作者最后更新于2020-12-20 10:35:55，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

前言

我是屑我是屑我是屑

我连多重背包01拆分都能写错

啊啊啊啊啊啊啊啊啊啊啊啊啊

思路

二合一题。

• 任务 $1$：计算一关的最大分数

一个很显然的 $dp$，我用了记忆化搜索实现。显然对于一个区间 $[l,r]$，最后选的数只能是 $a_l$ 或者 $a_r$，而最后选的数会创造 $r-l+1$ 的贡献。因此得到一个很显然的柿子：

$$dp_{i,j}=\max\{dp_{i+1,j}+a_i\times(j-i+1),dp_{i,j-1}+a_j\times (j-i+1)\} $$

• 任务 $2$：计算总分最大值

显然直接二进制分组多重背包即可。

一个小坑：这里的多重背包需要将前面所有的都选至少一次，所以 dp 的时候要先强制选一次，再自由选。

• 来讲一下我犯的 nt 错误：

• 大家都知道完全背包应该是

for(int i=1; i<=mx; mx-=i,i<<=1) 做一次i个物品的完全背包;
做一次mx个物品的完全背包;

• 然后我写了个

for(int i=1; i<=mx; i<<=1) if(i&mx) 做一次i个物品的完全背包;

• 一定要记住二进制拆分的原理啊/kel

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int c,mx,m,sdt,a[503];
long long dp[503][503];
long long ans[100003][2],Ans=0;
long long dfs(int l,int r)
{
	if(l==sdt&&r==sdt) return a[sdt];
	if(dp[l][r]) return dp[l][r];
	if(l==sdt) return dp[l][r]=dfs(l,r-1)+a[r]*(r-l+1);
	if(r==sdt) return dp[l][r]=dfs(l+1,r)+a[l]*(r-l+1);
	return dp[l][r]=max(dfs(l,r-1)+a[r]*(r-l+1),dfs(l+1,r)+a[l]*(r-l+1));
}
signed main()
{
	int n=read(),t=read(),sum=0;
	for(int i=1; i<=n; i++)
	{
		c=read(),mx=read()-1,m=read(),sdt=read(),sum+=c;
		for(int j=1; j<=m; j++) a[j]=read();
		memset(dp,0,sizeof(dp));
		long long DP=dfs(1,m);
		//printf("> %lld\n",dp[1][m]);
		for(int j=0; j<min(sum,t+1); j++) ans[j][i&1]=-1000000000000000ll;
		for(int j=t; j>=sum; j--) ans[j][i&1]=ans[j-c][(i&1)^1]+DP;
		for(int j=1; j<=mx; mx-=j,j<<=1)
		{
			long long g=DP*j;
			int h=j*c;
			for(int k=t; k>=h; k--) ans[k][i&1]=max(ans[k][i&1],ans[k-h][i&1]+g);
		} 
		long long g=DP*mx;
		int h=mx*c;
		for(int k=t; k>=h; k--) ans[k][i&1]=max(ans[k][i&1],ans[k-h][i&1]+g); 
		for(int j=1; j<=t; j++) Ans=max(Ans,ans[j][i&1]);
	}
	printf("%lld\n",Ans);
	return 0;
}