14211번: Kas

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

$O(ns)$ s: ci의 합

dp[i][j]: c[0...i]를 가지고 Kile합 - Pogi합이 j가 되도록 분배했을 때 사용하지 않은 총 금액의 최소

dp[0][0] = ci의 합, dp[0][j] = -inf (j!=0)
i>0이면 dp[i][j] = min(dp[i-1][j],dp[i-1][j+ci]-ci,dp[i-1][j-ci]-ci)

답은 (s + dp[n-1][0]) / 2

#include<cstdio>
#include<algorithm>
using namespace std;
int dp[100001], t[100001], a[500], n, s;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", a + i), s += a[i];
    fill(dp, dp + s + 1, 1e9);
    dp[0] = s;
    for (int i = 0; i < n; i++) {
        copy(dp, dp + 1 + s, t);
        for (int j = 0; j <= s; j++) {
            dp[j] = min(t[j], t[abs(j - a[i])] - a[i]);
            if (j + a[i] <= s) dp[j] = min(dp[j], dp[j + a[i]] - a[i]);
        }
    }
    printf("%d", s + dp[0] >> 1);
    return 0;
}