TIOJ-1197

, ,

排教室問題

https://tioj.ck.tp.edu.tw/problems/1197

Description

某校有M種不同的課程，其中有些課程的時間會有衝堂。如果學校中總共有N間不同的教室，請問共有多少種安排各課程上課教室的方式？最少要用到幾間教室？
$M,N \leq 10$

註: 衝堂的意思是他們不能被安排在同一個教室

Solution

題目可以想成給定一張圖，每個頂點有$k$種顏色可以塗，定義合法塗色是讓相鄰頂點無同色的塗色方式，問有幾種合法塗色的方式以及至少要用多少顏色才能合法塗色
一開始覺得這是暴搜題，但忽然想到可能不連通也可能會有環之後就不太知道怎麼實作
另外題敘好像沒有講到，不過這題讀邊的時候要用EOF讀

這題我的寫法是位元DP，考慮狀態$dp[S][c]$代表$c$之前的顏色都用過了，並且$S$這個subset已經被塗過了
那轉移可以想成把$S$的一個subset$X$都塗上$c$這個顏色，當然$X$中任意兩個頂點都不相鄰(也就是說$X$是獨立集)，式子長得像
$$
dp[S][c] = \sum\limits _ {X \subseteq S, Valid(X)} dp[S \setminus X][c-1]
$$
其中$Valid(X)$代表$X$是否為獨立集，可以先預處理
預處理獨立集可以做到$\mathcal{O}(n \cdot 2^n)$，而後面枚舉$k$次子集則是$\mathcal{O}(k \cdot 3^n)$

註: 一次枚舉複雜度是$\mathcal{O}(3^n)$的原因可以參考 https://cp-algorithms.com/algebra/all-submasks.html

AC code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 10;
typedef long long ll;

int k,n,a,b,valid[1<<N],g[N][N];
ll dp[1<<N][N];
signed main() {
    scanf("%d%d",&n,&k);
    while(~scanf("%d%d",&a,&b)) --a, --b, g[a][b] = g[b][a] = true;
    for(int s = 0; s < (1<<n); s++) valid[s] = true;
    for(int s = 0; s < (1<<n); s++) {
        for(int i = n-1; i >= 0; i--) if(s & (1<<i)) {
            if(!valid[s ^ (1<<i)]) valid[s] = false;
            for(int j = 0; j < i; j++) if(s & (1<<j)) if(g[i][j]) valid[s] = false;
            break;
        }
    }
    int ans = n;
    ll sum = 0;
    int S = (1<<n)-1;
    dp[0][0] = 1;
    for(int c = 1; c <= max(k,n); c++) {
        for(int s = 0; s < (1<<n); s++) {
            dp[s][c] = dp[s][c-1];
            for(int f = s; f; f = (f-1)&s) if(valid[f]) {
                dp[s][c] += dp[s^f][c-1];
            }
        }
        if(dp[S][c]) ans = min(ans, c);
    }
    printf("%lld\n%d\n",dp[S][k],ans);
}

話說雖然感覺會需要long long不過TIOJ上似乎沒有會超過int的測資

另外利用Fast Subset Convolution可以讓後面那部分從$\mathcal{O}(3^n)$壓到$\mathcal{O}(n^22^n)$
可以參考 https://people.csail.mit.edu/rrw/presentations/subset-conv.pdf
不過常數蠻大的，要$n$大一點才看得出來差異

comments powered by Disqus