如果直接处理的话，第$1$个小时是绝对不会有贡献的，
那么可以强制令第$n$个小时睡觉，第$1$个小时就会有贡献，因此进行两次DP，记录一下当前休不休息就好了。
转移状态就从前一个小时来就好了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
using namespace std;
const int N=3835;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int u[N],f[2][N][2];
int main()
{
    int n,m;qr(n),qr(m);
    for(int i=1;i<=n;i++)qr(u[i]);
    memset(f,0xcf,sizeof(f));
    f[1][0][0]=f[1][1][1]=0;
    for(int i=2;i<=n;i++)
        for(int j=0;j<=min(m,i);j++)
        {
                f[i&1][j][0]=max(f[i-1&1][j][0],f[i-1&1][j][1]);
                if(j-1>=0)f[i&1][j][1]=max(f[i-1&1][j-1][0],f[i-1&1][j-1][1]+u[i]);
        }
    int ans=max(f[n&1][m][1],f[n&1][m][0]);
    memset(f,0xcf,sizeof(f));
    f[1][1][1]=u[1];//强制第n小时睡觉
    for(int i=2;i<=n;i++)
        for(int j=1;j<=min(m,i);j++)
        {
                f[i&1][j][0]=max(f[i-1&1][j][0],f[i-1&1][j][1]);
                f[i&1][j][1]=max(f[i-1&1][j-1][0],f[i-1&1][j-1][1]+u[i]);
        }
    ans=max(f[n&1][m][1],ans);
    qw(ans);puts("");
    return 0;
}