2073번: 수도배관공사

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


$O(dp)$

dp[0]=inf
dp[j]=max(dp[j],min(dp[j-Li],Ci))

#include<cstdio>
#include<algorithm>
int d, p, dp[100001] = { 1 << 24 };
int main() {
    scanf("%d %d", &d, &p);
    for (int i = 0, x, y; i < p; i++) {
        scanf("%d %d", &x, &y);
        for (int j = d; j >= x; j--) dp[j] = std::max(dp[j], std::min(dp[j - x], y));
    }
    printf("%d", dp[d]);
    return 0;
}