素直に dp を考えると,
\(dp_{i,j} := \) \([0,i)\) まで見て,最後の休日が \(j\) 日目 のときの min.
しかし,これは失敗する. なぜなら,生産性は,今決めている日だけでなく,先の日の割り当て次第で 今日の近傍の生産性が変わってしまうから.
対策:
今が平日なら,生産性を 計上するのを保留しておく. 休日が来た日に,前回の休日からの生産性をまとめて計上する. これにより, 過去だけ分かっていれば十分となる.
休日同士の間が \(j\) 日で,間がすべて平日の場合, 生産性は \(\sum_{k \in j} a_{\lfloor k/2 \rfloor}\) となる.
実装:
初日を休日とする.
\(dp_{i,j} := \) \([0,i)\) 日まで見て,連続 \(j\) 日が平日であるときの min
とする.
\(for \ i \in n \) で dp を更新. ただし,\(n\) 日でループするので, ループの最後だけは初日が休日としたことと整合性が合うようにする.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m ;
cin >> n;
vll a(n); rep(i,n) { cin >> a[i]; }
vll s(n+2); rep(j,n+1) s[j+1] = s[j] + a[j/2];
vll dp(n, -INFL);
dp[0] = 0;
rep(i,n){
vll old(n, -INFL);
swap(dp, old);
drep(j,i+1){
if(i != n-1) chmax(dp[j+1], old[j]);
chmax(dp[0], old[j]+s[j]);
}
}
cout << dp[0] << endl;
return 0;
}