ABC285E动态规划动脑筋倒搜更好做

首先，第一个工作日选哪一天无所谓，生产力仅仅跟连续多少个工作日有关。
这样，我们就可以枚举工作日的间隔，上一个工作日是p，下一个工作日是i，当前空隙长度为i-p-1，后面可以没有工作日，也可以有工作日，暴力求解并记忆化即可。

#include <bits/stdc++.h>
#define N 5005
using namespace std;
int n, m, i, j, k;
long long s[N], f[N];
long long he(int n){
    long long v = s[n+1>>1];
    return n>1 ? v+s[n>>1] : v;
}//a仅仅用于计算生产力！！！
long long dfs(int p){
    long long i, m=he(n-p);
    if(f[p] != -1) return f[p];
    for(i=p+1; i<=n; i++){
        m = max(m, dfs(i)+he(i-p-1));
    }//增加(p, i)生产力，剩下递归求
    return f[p] = m;
}//p为最后工作日、枚举下一次的工作日
int main(){
    scanf("%d", &n);
    for(i=1; i<=n; i++){
        scanf("%d", &k);
        s[i] = s[i-1] + k;
    }//不妨设第一天为工作日
    memset(f, -1, sizeof(f));
    printf("%lld\n", dfs(1));
    return 0;
}

我们可以若干个格子填休息日，也可以n个格子填0和1，但内存开销更大：

#include <bits/stdc++.h>
#define N 5005
using namespace std;
int n, m, i, j, k;
long long ans, s[N], f[N][N];
long long he(int n){
    long long v = s[n+1>>1];
    return n>1 ? v+s[n>>1] : v;
}//a仅仅用于计算生产力！！！
long long dfs(int k, int p){
    if(k > n) return he(n-p);
    if(f[k][p] != -1) return f[k][p];
    long long x=dfs(k+1, p), y;
    y = dfs(k+1, k) + he(k-p-1);
    return f[k][p] = x>y ? x : y;
}//n个格子填01，第k个，上一个1是p 
int main(){
    scanf("%d", &n);
    for(i=1; i<=n; i++){
        scanf("%d", &k);
        s[i] = s[i-1] + k;
    }//不妨设第一天为工作日
    memset(f, -1, sizeof(f));
    printf("%lld\n", dfs(2, 1));
    return 0;
}