1423번: 원숭이 키우기 - bounded knapscak problem으로 풀어보기

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


저지 사이트에 언급 되지 않은 몇 가지 유의사항이 있다.
- 캐릭터 수는 d를 넘을 수 있다.
- 캐릭터 수가 매우 많을 수 있으므로 답은 int 범위가 넘어갈 수 있다.


$O(n^2d^2)$

일단 초기 힘의 합을 구해 놓는다. 그리고 훈련 기간보다 많은 사람을 훈련시킬 수 없으므로 캐릭터 수가 d보다 크다면 d라고 가정한다.
이제
dp[훈련기간]: 해당 훈련 기간이내 추가할 수 있는 최대 힘의 합
이라고 정의한 점화식을 knapsack problem 해결법 비슷하게 풀 수 있다.
해당 기간에서 각 캐릭터가 얼만큼 레벨을 올리는 지에 따라 dp 배열을 갱신해나가면 문제를 해결할 수 있다. 캐릭터의 총 수는 최대 nd이므로 시간 안에 해결할 수 있을 것이다.
구현은 해보지 않았지만 bounded knapsack problem 해결법을 이용한다면 $n^2d$시간에도 가능할 듯하다.

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long lint;
int n, d, p[51], q[51];
lint r, dp[101];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", p + i);
    for (int i = 1; i <= n; i++) scanf("%d", q + i);
    scanf("%d", &d);
    for (int i = 1; i <= n; i++) r += (lint)p[i] * q[i], p[i] = min(d, p[i]);
    for (int i = 1; i <= n; i++)
        while (p[i]--) for (int j = d; j >= 0; j--)
            for (int k = i + 1; k <= n&&k + j - i <= d; k++)
                dp[k + j - i] = max(dp[k + j - i], dp[j] + q[k] - q[i]);
    printf("%lld", dp[d] + r);
    return 0;
}