题解 SP283 【NAPTIME - Naptime】

· · 题解

【分析过程】

我们可以用一个三维数组 f_{i,o,p} 来表示状态

其中 i 表示经过了的时间段，o 表示已经睡了 o 个时间段，p 表示这个时间段有没有在睡觉

那么对于一个时间段有两种决策：睡觉或是不睡觉

所以我们可以推出转移方程：

f_{i,o,0}=\max(f_{i-1,o,0},f_{i-1,o,1}) f_{i,o,1}=\max(f_{i-1,o-1,0},f_{i-1,o-1,1}+v_i)

因为此题是一个环形动态规划，所以我们选择强制断环然后强制连环进行两次动态规划来消除后效性

断环，意即在时间 N 不睡觉，所以额外初始化为 f_{1,1,1}=0

连环，意即在时间 N 和次日时间 1 的时候强制睡觉，所以额外初始化为 f_{1,1,1}=v_1，统计答案的时候为 ans=\max(ans,f_{n,m,1})

【代码实现】

#include<iostream>
#include<cstring>
#define N 4000
#define set(f) memset(f,-0x3f,sizeof(f))
#define cl(a) for(int i=1;i<=n;i++) a[i][0][0]=0;
using namespace std;
int n,in[N],T,b,ans,f[N][N][2];
signed main(){
    cin>>T;
    while(T--){ans=0;
    cin>>n>>b;
    for(int i=1;i<=n;i++){
        cin>>in[i];
    }
    set(f);cl(f);
    f[1][1][1]=0;
    for(int i=2;i<=n;i++){
        for(int o=1;o<=i;o++){
            f[i][o][0]=max(f[i-1][o][0],f[i-1][o][1]);
            f[i][o][1]=max(f[i-1][o-1][1]+in[i],f[i-1][o-1][0]);
        }
    }
    ans=max(f[n][b][0],f[n][b][1]);
    set(f);cl(f);
    f[1][1][1]=in[1];
    for(int i=2;i<=n;i++){
        for(int o=1;o<=i;o++){
            f[i][o][0]=max(f[i-1][o][0],f[i-1][o][1]);
            f[i][o][1]=max(f[i-1][o-1][1]+in[i],f[i-1][o-1][0]);
        }
    }
    cout<<max(ans,f[n][b][1])<<"\n";
    }
}