题解

核心是把环形dp转化成两次线性dp。具体如何实现的呢？不考虑环形的话会遗漏一种情况，就是时间片1是睡着了的，所以第二次dp的时候把时间片n和1设置为入睡，具体操作为初始化dp[1][1][1]=utility[1]，更新答案的时候只更dp[n&1][b][1]。

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=4e3;
const int INF=0x3f3f3f3f;
int dp[2][N][2];
int n,b;
int u[N];
int ans=0;
int main()
{
    cin>>n>>b;
    for(int i=1;i<=n;++i)
        cin>>u[i];
    memset(dp,-INF,sizeof(dp));
    dp[0][0][0]=dp[1][1][1]=dp[1][0][0]=0;
    for(int i=2;i<=n;++i)           //start from 2
    {
        int k=i&1;
        for(int j=1;j<=i;++j)
        {
            dp[k][j][0]=max(dp[k^1][j][0],dp[k^1][j][1]);
            dp[k][j][1]=max(dp[k^1][j-1][0],dp[k^1][j-1][1]+u[i]);
        }
    }
    ans=max(dp[n&1][b][0],dp[n&1][b][1]);
    memset(dp,-INF,sizeof(dp));
    dp[1][1][1]=u[1];
    dp[0][0][0]=dp[1][0][0]=0;
    for(int i=2;i<=n;++i)
    {
        int k=i&1;
        for(int j=1;j<=i;++j)       //here
        {
            dp[k][j][0]=max(dp[k^1][j][0],dp[k^1][j][1]);
            dp[k][j][1]=max(dp[k^1][j-1][0],dp[k^1][j-1][1]+u[i]);
        }
    }
    ans=max(ans,dp[n&1][b][1]);
    cout<<ans<<endl;
    return 0;
 
 
 
}