自动搬运

查看原文

来自洛谷，原作者为

	Andy_Lin **

搬运于2025-08-24 22:17:03，当前版本为作者最后更新于2020-03-28 15:34:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

双倍经验

先来考虑一个“简化版”：假设第N个小时与次日第一个小时不是相连的，那么这就是一个明显的DP题：

用$dp_{i,j,0/1}$来表示在第i个小时，已经休息了j个小时，0表示这个小时没在休息，1表示这个小时正在休息。

状态转移方程就是：

dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]);
dp[i][j][1]=max(dp[i-1][j-1][0],dp[i-1][j-1][1]+u[i]);

初值：$dp_{1,1,1}=0$，$dp_{1,0,0}=0$，其余为-INF。

答案：$\max(dp_{n,b,0},dp_{n,b,1})$。

但问题是第N个小时与次日第一个小时是相连的，上面的方法不能直接用。既然这样，那就再来一次强制连接：

强制让第N个小时睡觉，让次日第一个小时熟睡。

状态转移方程如上。

初值：$dp_{1,1,1}=u_{1}$，$dp_{1,0,0}=0$，其余为-INF。

答案：$dp_{n,b,1}$

具体来说，我们可以先将第N个小时与次日第一个小时断开，然后用上面的“简化版”的方法来得到一个答案。再强制让第N个小时睡觉，让次日第一个小时熟睡，用上面讨论的强制连接的方法得到第二个答案，两者取最大值即可。

$AC\ Code:$

#include<bits/stdc++.h>
using namespace std;
int dp[3831][3831][2],n,b,u[3831],ans;
int main() {
	scanf("%d%d",&n,&b);
	for(int i=1;i<=n;i++)scanf("%d",u+i);
	memset(dp,-0x3f,sizeof(dp));
	dp[1][1][1]=dp[1][0][0]=0;
	for(int i=2;i<=n;i++){
		dp[i][0][0]=dp[i-1][0][0];
		for(int j=1;j<=b;j++){
			dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]);
			dp[i][j][1]=max(dp[i-1][j-1][0],dp[i-1][j-1][1]+u[i]);
		}
	}
	ans=max(dp[n][b][0],dp[n][b][1]);
	memset(dp,-0x3f,sizeof(dp));
	dp[1][1][1]=u[1];
	dp[1][0][0]=0;
	for(int i=2;i<=n;i++){
		dp[i][0][0]=dp[i-1][0][0];
		for(int j=1;j<=b;j++){
			dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]);
			dp[i][j][1]=max(dp[i-1][j-1][0],dp[i-1][j-1][1]+u[i]);
		}
	}
	ans=max(ans,dp[n][b][1]);
	printf("%d\n",ans);
	return 0;
}

这是一个比较常见的解决环形DP的策略，一定要记住