1126번: 같은 탑

https://www.acmicpc.net/problem/1126


$O(nS)$

dp[i][j]: $1...i$ 번 블럭을 이용하여 $h_A-h_B=j$가 되도록 만들 때 $h_A$의 최댓값

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXD = 25e4;
int n, dp[51][MXD * 2 + 1], a[51];
bool vis[51][MXD * 2 + 1];
int f(int h, int d) {
    if (!h || abs(d - MXD) > MXD) return d^MXD ? -1e9 : 0;
    if (!vis[h][d]) {
        vis[h][d] = 1;
        dp[h][d] = max({ f(h - 1, d - a[h]) + a[h], f(h - 1, d + a[h]),f(h - 1,d) });
    }
    return dp[h][d];
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    int r = f(n, MXD);
    printf("%d", r ? r : -1);
    return 0;
}