https://atcoder.jp/contests/abc285/tasks/abc285_e

Let the first day be weekend, then day $n+1$ is also weekend.

Let $dp[i][j]$ represents the max productivity on the first $i$ days while the last weekend is $j$-th day.

$$dp[i][j]=\{\begin{array}{ll}max\{dp[k][k]+c(j+1,i-1)\},k\in [1,i),& j=i\\ dp[i-1][j]+a[min(i-j,n+1-i)],& j<i\end{array}$$

that is in each stage we have two decisions:

• assign day $i$ weekday, then find the max productivity and update day $i$
• assign day $i$ weekend, then find the max productivity and update interval $(j,i)$

// compile: g++ -o data data.cpp -O3 -std=gnu++20 -Wall -Wextra -Wshadow -D_GLIBCXX_ASSERTIONS -ggdb3 -fmax-errors=2 -DLOCAL
// run: ./data < data.in
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#ifdef LOCAL
#include <debug/codeforces.h>
#define debug(x...) {_variables(#x);_print(x);}
#else
#define debug(x...)
#endif
template<typename...Args> void print_(Args...args){((cout<<args<<" "),...)<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define sz(v) ((int)(v).size())
#define print(...) print_(__VA_ARGS__);
#define INTINF (int)(9223372036854775807)
#define int long long
#define MAXN 5010
 
int n, a[MAXN], s[MAXN];
int dp[MAXN][MAXN];
 
int get(int l, int r) {
    int days = r - l + 1;
    return 2 * s[days >> 1] + ((days & 1) * (a[(days >> 1) + 1]));
}
 
int32_t main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
 
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i], s[i] = s[i-1] + a[i];
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j < i; ++j) {
            dp[i][i] = max(dp[i][i], dp[j][j] + get(j+1, i-1));
            dp[i][j] = dp[i-1][j] + a[min(i-j, n+1-i)];
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) ans = max(ans, dp[n][i]);
    cout << ans << endl;
 
    return 0;
}

				

					
				
				

					
				
				

					
				
				

					
				
			

The problem is easy but took me more than 20 mins.

1. When encountering cyclic DP problems, try to break the cycle.
2. Think carefully about the states, whether there are multiple ways to express it? try to use the one with the simplest state transition function.