각 시간대마다 필요한 알바 수와 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)$
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; }
