BOJ)7579 앱

문제: icpc.me/7579

최소한의 비용을 사용하여 m만큼의 메모리를 얻을 때 비용을 출력하는 문제이다.

dp[pos][cost]= pos번째 앱까지 cost만큼의 비용을 사용해 얻을 수 있는 메모리의 최댓값으로 정의 한 뒤

파라메트릭 서치를 이용하여 cost값을 조정해주면 된다.

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, cost, m[101], c[101], dp[101][10001];
int func(int pos, int cos) {
    if (pos < 0)return 0;
    int &ret = dp[pos][cos];
    if (ret != -1)return ret;
    ret = func(pos - 1, cos);
    if (cos - c[pos] >= 0)
        ret = max(ret, func(pos - 1, cos - c[pos]) + m[pos]);
    return ret;
}
int main() {
    scanf("%d%d", &n, &cost);
    int lo = 0, hi = 0;
    for (int i = 0; i < n; i++)
        scanf("%d", &m[i]);
    for (int i = 0; i < n; i++) {
        scanf("%d", &c[i]);
        hi += c[i];
    }
    memset(dp, -1, sizeof(dp));
    while (lo < hi) {
        int mid = (lo + hi) >> 1;
        if (func(n - 1, mid) >= cost)
            hi = mid;
        else
            lo = mid + 1;
    }
    printf("%d\n", lo);
    return 0;
}