2237번: 수열 축소

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

$O(nT)$ // T: t가 가능한 구간 크기

축소 연산을 통해 A[1] - A[2]에 나머지 항들(A[3..n])을 더하거나 빼서 나오는 수를 모두 만들 수 있다.
이를 수식으로 쓰고 A[2..n] 앞에 있는 부호를 나열해보면 1개의 -와 뒤이은 0개 이상의 +들 묶음들로 이루어졌다는 것을 알 수 있다.
앞에서 부터 각 묶음에 대해 +가 x개이면 순서대로 i = 2를 x번, i = 1을 1번 축소 연산을 수행하면 된다.

#include<cstdio>
int n, t, a[101], dp[101][20001], r[101];
int main() {
    scanf("%d%d", &n, &t);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    dp[2][a[1] - a[2] + 10000] = 1;
    for (int i = 3; i <= n; i++)
        for (int j = 0; j < 20001; j++)
            if (dp[i - 1][j]) dp[i][j - a[i]] = 1, dp[i][j + a[i]] = 2;
    for (int i = n, p = t + 10000; i > 1; i--) {
        r[i] = dp[i][p];
        p = r[i] - 1 ? p - a[i] : p + a[i];
    }
    for (int i = 3; i <= n; i++) printf("%d\n", r[i]);
    puts("1");
    return 0;
}