Educational Codeforces Round 92 (Rated for Div. 2)B-Array Walk

제목
당신 에 게 서열 을 하나 드 리 겠 습 니 다. 당신 은 k 번 조작 을 할 수 있 습 니 다.그 중에서 z 회 왼쪽으로 조작 할 수 있 지만 연속 적 인 왼쪽으로 조작 할 수 없다.
사고의 방향
전이 방정식 은 비교적 쉽게 생각해 낼 수 있다.
d p [i] [j] dp [i] [j] dp [i] [j] 는 i i 위 에서 j j j 차 를 왼쪽으로 조작 하 는 것 을 나타 낸다.
오른쪽으로: d p [i] [j] = ma x (d p [i] [i]] [j], d p [i − 1] [j] + a [j]]] dp[i]] [j]]] [j]]] [j] = max (dp[i]] [j] + a [j]]] [j] + a [j], dp[i]] [j]], dp[i − 1] [j] + a [j] + a [j] [j] + a [j] 왼쪽으로: d p [i] [i] = m a x [i] = m a x (d p [i] [j]], d p [i + 1] [j − 1] [j]] [j]]] + a] + a [j]] + a [j]]]]] [j] = max (dp [i] [j], dp [+ 1] [j - 1] + a [j]) dp [i] = max (dp [i] [j], dp [+ 1] [j - 1] + a [j])상태 전이 방정식 에 따라 순환 을 정할 수 있다.
그 다음 에 순환 에서 조건 이 걸음 수가 k 보다 작은 지 판단 한 다음 에 dp 에서 ans 를 업데이트 합 니 다.

#include 
#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define endl '
'
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(case, x) cout << case << "  : " << x << endl
#define open freopen("ii.txt", "r", stdin)
#define close freopen("oo.txt", "w", stdout)
#define IO                       \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0)
#define pb push_back
using namespace std;
//#define int long long
#define lson rt << 1
#define rson rt << 1 | 1
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> PII;
const int maxn = 1e5 + 10;

ll a[maxn], dp[maxn][6];

void solve(){
    int n, k, z;
    cin >> n >> k >> z;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        dp[i][0] = dp[i - 1][0] + a[i];
        for (int j = 1; j <= z; ++j) dp[i][j] = 0;
    }

    //dp[i][j]=max(dp[i][j],dp[i-1][j]+a[j]);
    //dp[i][j]=max(dp[i][j],dp[i+1][j-1]+a[j]);
    ll ans = dp[k + 1][0];
    for (int j = 1; j <= z;++j){
        for (int i = 1; i <= n;++i){
            if(2*j+i-1<=k){
                dp[i][j] = max(dp[i][j], dp[i - 1][j] + a[i]);
                dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + a[i]);
            }
            ans = max(dp[i][j], ans);
        }
    }
    cout << ans << endl;
}

int main(){
    int t;cin>>t;
    while(t--){
        solve();
    }

    return 0;
}