《算法竞赛进阶指南》0x55环形及后效性处理DP 休息时间

一个DP问题：一天24小时连续，0——1为第1小时，每天有n个小时，每个小时都有一个睡眠收益，问睡m个小时最多获得的收益是多少。

由于这是一个环状的问题，每个时刻可能在睡觉也可能不在睡觉，为了去掉环状结构，可以将决策分成第n个小时在睡觉和第n个小时不在睡觉，状态F[i,j,0/1]表示从第1个小时开始，前i个小时睡了j小时，并且第i个小时在睡觉和第i个小时不在睡觉的最大收益。两种决策不同的是初值，最终只要取F[n,m,0]或者F[n,m,1]即可。

由于内存64M的限制，所以数组可以通过滚动进行优化。1e7的int所占的空间大约是40M。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 4000;
int w[maxn];
int f[2][maxn][2];
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>w[i];
    
    //第N小时不在睡觉
    memset(f,-0x3f,sizeof f);
    int ans=-1;
    f[1][0][0]=f[1][1][1]=0;
    for(int i=2;i<=n;i++){
        for(int j=0;j<=m;j++){
            f[i & 1][j][0]=max(f[i-1 & 1][j][0],f[i-1 & 1][j][1]);
            if(j)f[i & 1][j][1]=max(f[i-1 & 1][j-1][0],f[i-1 & 1][j-1][1]+w[i]);
        }
    } 
    ans=max(ans,f[n & 1][m][0]);
    memset(f,-0x3f,sizeof f);
    f[1][0][0]=0;
    f[1][1][1]=w[1];
    for(int i=2;i<=n;i++){
        for(int j=0;j<=m;j++){
            f[i & 1][j][0]=max(f[i-1 & 1][j][0],f[i-1 & 1][j][1]);
            if(j)f[i & 1][j][1]=max(f[i-1 & 1][j-1][0],f[i-1 & 1][j-1][1]+w[i]);
        }
    } 
    ans=max(ans,f[n & 1][m][1]);
    
    cout<<ans<<endl;
}

《算法竞赛进阶指南》0x55环形及后效性处理DP 休息时间

相关推荐