PROG-1093: หยิบหนังสือ

#include <bits/stdc++.h>

using namespace std;
const int INF = 1e9;
const int N = 2e3 + 1;
int dp[2][N];
int ar[N];
int n;

int f(int i, int s){

    if(i == n + 1){
        if(s == 0) return 0;
        else return -INF;
    }

    if(dp[i][s] != -INF) return dp[i][s];

    dp[i][s] = ar[i] + f(i + 1, s + 1);
    if(s == 0) dp[i][s] = max(dp[i][s], f(i + 1, s));
    if(s >= 2) dp[i][s] = max(dp[i][s], - ar[i] + f(i + 1, s - 2));

    return dp[i][s];
}

int main(){

    scanf("%d", &n);

    for(int i=1;i<=n;i++){
        scanf("%d", &ar[i]);
    }

    int pre, cur;
    cur = (n + 1) % 2;
    dp[cur][0] = 0;
    for(int s=1;s<=n;s++){
        dp[cur][s] = -INF;
    }

    for(int i=n;i>=1;i--){
        pre = (i + 1) % 2;
        cur = i % 2;
        for(int s=n;s>=0;s--){
            dp[cur][s] = ar[i] + dp[pre][s + 1];
            if(s == 0) dp[cur][s] = max(dp[cur][s], dp[pre][s]);
            if(s >= 2) dp[cur][s] = max(dp[cur][s], - ar[i] + dp[pre][s - 2]);
        }
    }

    printf("%d", dp[1][0]);

    return 0;
}