[2281] 데스노트

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

2281번: 데스노트

dp(i, j) = i번째 이름의 마지막 문자가 j번째 열에서 끝났을때의 최적해로 놓고,

i번째 이름을 새로운 행에 쓰는 경우는 항상 고려하며,

i번째 이름을 기존의 행에 이어서 쓰는 경우에는, (남은 칸)+(i번째 이름의 길이)<=m인 경우에만 고려한다.

실제로는 공백을 두어야 하므로, 재귀로 넘길때에는 (남은 칸)+(i번째 이름의 길이)+1을 넘기게 되는데

이 경우 열을 나타내는 인자가 일시적으로 m을 초과할 수 있다. 이 경우만 별도로 분기해주었다.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

int n, m, dp[1001][1001];

vector<int> v;

int f(int i, int c) {

    if (i >= n) return 0;

    if (dp[i][c] != -1) return dp[i][c];

    if (c == m + 1) return f(i, 0);

    dp[i][c] = (m - c + 1) * (m - c + 1) + f(i + 1, v[i] + 1);

    if (c + v[i] <= m) dp[i][c] = min(f(i + 1, c + v[i] + 1), dp[i][c]);

    return dp[i][c];

}

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n >> m;

    v.resize(n);

    int i;

    for (i = 0; i < n; i++) cin >> v[i];

    memset(dp, -1, sizeof(dp));

    cout << f(0, 0);

    return 0;

}

---