7332번: Cashier Employment

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

각 시간대마다 필요한 알바 수와 8시간동안 연속적으로 고용할 수 있는 알바 정보가 주어졌을 때 필요한 알바 수의 최솟값을 구하는 문제이다.

r[i]: i-1 ~ i시에 필요한 알바 수
t[i]: i-1 ~ i+7시에 쓸 수 있는 알바 수
* 굳이 i-1로 한 이유는 후에 prefix sum을 사용하는데 있어 -1번째 인덱스가 나오지 않게 하기 위함이다.

그러면 문제는 0<= a[i] <= t[i]인 a[i]를 잘 골라
i<8 일 때, a[17+i] + ... + a[24] + a[1] + ... + a[i] >= r[i]
i>=8 일 때, a[i-7] + a[i-6] + ... + a[i] >= r[i]
를 만족하는 sum(a[i])의 최솟값을 구하는 문제라고 할 수 있다.

s[i] = sum(a[j]: 1<=j<=i)로 놓고 모든 조건을 일차선형부등식 꼴로 만들어 보면
0 <= s[i] - s[i-1] <= t[i]
i<8 일 때, s[24] - s[16+i] + s[i] >= r[i]
i>=8 일 때, s[i] - s[i-8] >= r[i]

이제 상수 lmt <= s[24]로 놓으면

s[24] - lmt >= s[0]

s[i] >= s[i-1]

s[i-1] + t[i] >= s[i]

i<8 일 때, s[i] + lmt - r[i] >= s[16+i]
i>=8 일 때, s[i] - r[i] >= s[i-8]

모든 부등식이 x + w >= y 꼴의 형태이므로 각 조건에 대응되는 가중치가 w인 x -> y 간선들을 추가한 뒤, 최단거리 알고리즘을 이용해 주어진 부등식들이 가능한지 판단할 수 있다.
부등식들이 모두 성립하는 최소 0 <= lmt <= n를 찾는다. 불가능하면 No Solution을 출력한다.

시간복잡도는 테스트 케이스마다 $O(n)$

#include<cstdio>
#include<algorithm>
using namespace std;
int tc, n, t[25], r[25], dp[25][25];
bool f(int lmt) {
    fill(dp[0], dp[25], 1e9);
    for (int i = 0; i < 25; i++) {
        dp[i][i] = 0;
        if (i) dp[i - 1][i] = t[i], dp[i][i - 1] = 0;
    }
    int i = 1;
    for (; i < 8; i++) dp[i][i + 16] = lmt - r[i];
    for (; i < 25; i++) dp[i][i - 8] = -r[i];
    dp[24][0] = -lmt;
    for (int i = 0; i < 25; i++) for (int j = 0; j < 25; j++) for (int k = 0; k < 25; k++) dp[j][k] = min(dp[j][k], dp[j][i] + dp[i][k]);
    for (int i = 0; i < 25; i++) if (dp[i][i] < 0) return false;
    return true;
}
void task() {
    for (int i = 1; i <= 24; i++) scanf("%d", r + i), t[i] = 0;
    scanf("%d", &n);
    for (int i = 0, x; i < n; i++) scanf("%d", &x), t[x + 1]++;
    for (int i = 0; i <= n; i++) if (f(i)) { printf("%d\n", i); return; }
    puts("No Solution");
}
int main() {
    for (scanf("%d", &tc); tc--;) task();
    return 0;
}