【Naptime G】环形dp模板题

贝茜是一只非常颓废的奶牛．她的一天被平均分割成 N N N 段（ 3 ≤ N ≤ 3830 3 leq N leq 3830 3≤N≤3830），但是她要用其中的 B B B 段时间（ 2 ≤ B < N 2 leq B lt N 2≤B

有了闹钟的帮助，贝茜可以选择任意的时间开摆，当然，她只能在时间划分的边界处开摆、开卷。

贝茜想使所有摆烂效用的总和最大。不幸的是，每一段摆烂的第一个时间阶段都是“开摆”阶段，而旦不记入效用值。

时间阶段是不断循环的圆（一天一天是循环的嘛），假如贝茜在时间 N N N 和时间 1 1 1 摆烂，那么她将得到时间 1 1 1 的效用值。

第一行两个整数 N , B N,B N,B。

接下来 N N N 行，每行一个整数，表示第 i i i 个时段的效用值。

输出最大效用值。

5 3
2
0
3
1
4

6

从第 4 4 4 个时段开摆，到第 1 1 1 个时段结束开卷。

考虑一个简化的问题，不考虑摆烂跨越两天的情况，即：
状态f[i,j,k]：前 i i i 个小时中一共睡了 j j j 个小时，且第 i i i 个小时的摆烂状态为 k k k （1睡，0不睡）。
状态转移：

F [ i , j , 0 ] = M A X ( F [ i − 1 , j , 0 ] , F [ i − 1 , j , 1 ] ) F[i,j,0]=MAX(F[i-1,j,0],F[i-1,j,1]) F[i,j,0]=MAX(F[i−1,j,0],F[i−1,j,1])
F [ i , j , 1 ] = M A X ( F [ i − 1 , j − 1 , 0 ] , F [ i − 1 , j − 1 , 1 ] + U i ) F[i,j,1]=MAX(F[i-1,j-1,0],F[i-1,j-1,1]+U_i) F[i,j,1]=MAX(F[i−1,j−1,0],F[i−1,j−1,1]+Ui​)

很好理解，但这种情况下有一种问题：每天最早1点开摆，此时的效用值无法计入总数。

那再思考另一种情况，强制它前一天第 N N N 个小时和当天第 1 1 1个小时摆烂，那么第 1 1 1 个小时的效用值就可以计算上了。

把分成的两部分分别dp最后取 M A X MAX MAX 即为答案。

CODE：

#include
#include
using namespace std;
int n,b;
int val[3850];
int dp[3850][3850][2],ans;

int main(){
	cin>>n>>b;
	for(int i=1;i<=n;i++)cin>>val[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]+val[i]);
		}
	}
	ans=max(dp[n][b][0],dp[n][b][1]);
	
	memset(dp,-0x3f,sizeof dp);
	dp[1][1][1]=val[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]+val[i]);
		}
	}
	ans=max(ans,dp[n][b][1]);//第N个小时必须得摆！
	
	cout< 
在以上的基础上再进行滚动数组的优化，使空间复杂的 
    
     
      
       
        
         n
        
        
         2
        
       
       
        →
       
       
        n
       
      
      
       n^2→n
      
     
    n2→n 。
 
#include
#include
using namespace std;
int n, b;
int val[3850];
int dp[2][3850][2], ans;

int main() {
	cin >> n >> b;
	for (int i = 1; i <= n; i++)cin >> val[i];

	memset(dp, -0x3f, sizeof dp);
	dp[1][1][1] = dp[1][0][0] = 0;
	
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= b; j++) {
			dp[i & 1][j][0] = max(dp[(i - 1) & 1][j][0], dp[(i - 1) & 1][j][1]);
			if(j >= 1)dp[i & 1][j][1] = max(dp[(i - 1) & 1][j - 1][0], dp[(i - 1) & 1][j - 1][1] + val[i]);
		}
	}
	ans = dp[n & 1][b][0];

	memset(dp, -0x3f, sizeof dp);
	dp[1][1][1] = val[1]; //第1个小时也记上了！
	dp[1][0][0] = 0;
	
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= b; j++) {
			dp[i & 1][j][0] = max(dp[(i - 1) & 1][j][0], dp[(i - 1) & 1][j][1]);
			if(j >= 1)dp[i & 1][j][1] = max(dp[(i - 1) & 1][j - 1][0], dp[(i - 1) & 1][j - 1][1] + val[i]);
		}
	}
	ans = max(ans, dp[n & 1][b][1]); //第N个小时必须得摆！

	cout << ans;

	return 0;
}