D - equeue

問題

要素のdequeue が与えられる.push_back,push_front,pop_back,pop_frontを合計回行うことができる。
取り出した要素の和を最大化せよ。
atcoder.jp

解法

・push,popを貪欲に決めるのは難しいそう。例えば負の要素は取りたくないが、あえて取ることで後ろの正の要素を取れる。
・重要な考察として、正の要素を再度pushする必要はない。負の要素はpushすることで、和を大きくすることができるがこれは最後に行えば良い。
・これより、負の要素はコストを2払うことで、単に捨てる動作とすることができる
・DPで解ける。として、は次に見る左の要素、は次に見る右の要素

・追加する要素の場合は、コストを二つ使ってそのまま推移させればよい。
・ の部分がうまく推移できなかったので、最後の部分で計算した。このあたりもっと良い方法がありそう

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define INF (sizeof(int) == 4 ? (int)1e9:(int)1e18)
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
signed main(){
    int n,k; cin >> n >> k;
    vector<int>v(n);
    for(auto & e : v) cin >> e;
    auto dp = vectors(n,n,k,-INF);
    if(k == 1 or n == 1){
        cout << max({v.front(),v.back(),0LL}) << endl;
        return 0;
    }
    dp[1][n - 1][k -  1] = v.front();
    dp[0][n - 2][k -  1] = v.back();
    if(v.front() < 0 and k >= 2){
        dp[1][n - 1][k - 2] = 0LL;
    } else if(v.back() < 0 and k >= 2){
        dp[0][n - 2][k - 2] = 0LL;
    }
    auto valid = [&](int l,int r){ return (l <= r and 0 <= l and  r <= n-1);};
    for(int l = 0; l < n; ++l){
        for(int r = n - 1; r >= 0; --r){
            for(int cst = 1; cst < k; ++cst){
                if( dp[l][r][cst] == -INF) continue;
                int now = dp[l][r][cst];
                if( valid(l + 1,r) )
                    cmax(dp[l + 1][r][cst - 1],now + v[l]);
                if( valid(l,r - 1) )
                    cmax(dp[l][r - 1][cst - 1],now + v[r]);
                if(v[l] < 0 and  valid(l + 1,r) and cst >= 2)
                    cmax(dp[l + 1][r][cst - 2],now);
                if(v[r] < 0 and valid(l,r - 1) and cst >=2)
                    cmax(dp[l][r - 1][cst - 2],now);
            }
        }
    }
    int ans = 0;
    for(int l = 0; l < n; ++l){
        for(int r = 0; r < n; ++r){
            for(int cst = 0; cst < k; ++cst){
                cmax(ans,dp[l][r][cst]);
                if(l == r){
                    cmax(ans,dp[l][r][cst] + (cst != 0 and v[l] > 0 ? v[l] : 0));
                }
            }
        }
    }
    cout << ans << endl;
}