题目#

hpuoj-74

codeforces-568-G1

题解#

两个题目都是状压DP，有一定的相似之处，放在一起写。

第一题#

显然，对于每个宿舍楼内部的宿舍来说，当顺序固定了以后，可以简单的通过贪心得到最少抗议的人数。

那么，我们的主要问题就变成了，求解宿舍楼安装空调最合适的顺序。

定义 $dp[sta]$ 表示状态为 $sta$ 时的最少抗议人数， $cost[i][j]$ 表示第 $i$ 幢寝室楼第 $j$ 个空调的贪心值。

那么我们可以这样更新：

1
for sta := 0 to (1<<n)-1 do
2
  cal = sta.count(1)
3
  for  nex := 0 to n-1 do
4
    if (sta>>nex)&1
5
      then continue
6
    else
7
      dp[sta|1<<nex] = min(dp[sta|1<<nex], dp[sta] + cost[nex][cal+1])

结果就是 $dp[(1<<n)-1]$ 。

这样更新的理由是：

对于一个状态 $sta$ ，用1表示宿舍楼已经被安排过位置了，0表示还没有安排，统计一下1的个数就能知道在这个状态下，下一个宿舍楼是第几个被装的，而且这个宿舍楼之前一定是没有装过。

例如：

$n = 4, sta = 1001$ ，下一个要装第三个宿舍楼，而二号、三号宿舍楼还没有装。

因此可以更新到 $sta = 1101, 1011$ 这两个状态。

第二题#

方法一#

定义 $dp[cap][sta][last]$ 表示当前总和为 $cap$ ，状态为 $sta$ ，最后一首歌的类型为 $last$ ，然后直接维护更新就好了。

时间复杂度：O(T*n*2^n)

方法二#

定义 $dp[sta][last]$ 表示当前状态为 $sta$ ，最后一首歌的类型为 $last$ ，进行一下更新：

1
for sta := 0 to (1<<n)-1 do
2
  for i := 1 to n do
3
    if (sta>>i)&1
4
      then continue
5
    for type := 1 to 3 do
6
      if type == last[i]
7
        then continue
8
      dp[sta|1<<(i-1)][last[i]] += dp[sta][type]

这样就能得到所有的情况，但是不一定每一种情况的 $cap$ 都是 $T$ ，所以我们在求和的时候进行判断：

1
sum = 0
2
for sta := 0 to (1<<n)-1 do
3
  cap = 0
4
  for i := 1 to n do
5
    if (sta>>i)&1
6
      then  cap += t[i]
7
  if cap == T
8
    then
9
      for type := 1 to 3 do
10
        sum += dp[sta][type]

时间复杂度：O(n*2^n)

代码#

第一题#

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef pair<int, int > pii;
5
inline ll qpow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res = (res*a)%mod;a=(a*a)%mod;b>>=1;}return res;}
6
const int mod = 1e9 + 7;
7
const int MAXN = 2e5 + 7;
8

9
int dp[1<<23];
10
int f[23][2333];
11
int a[23][23];
12

13
int main(){
14
    #ifndef ONLINE_JUDGE
15
        freopen("in.txt", "r", stdin);
16
        freopen("out.txt", "w", stdout);
17
    #endif
18

19
    int n, m;
20
    cin >> n >> m;
21
    for(int i = 1; i <= n; ++i){
22
        for(int j = 1; j <= m; ++j){
23
            cin >> f[i][j];
24
        }
25
        sort(f[i]+1, f[i]+1+m);
26
    }
27
    for(int i = 1; i <= n; ++i){
28
        for(int j = 1; j <= n; ++j){
29
            int cur = (j-1)*m + 1, res = 0;
30
            for(int k = 1; k <= m; ++k){
31
                if(f[i][k] >= cur){
32
                    cur++;
33
                } else res++;
34
            }
35
            a[i][j] = res;
36
        }
37
    }
38
    memset(dp, 0x3f, sizeof dp);
39
    dp[0] = 0;
40
    function<int(int)> cal = [&](int x){
41
        int res = 0;
42
        while(x){
43
            res += x&1;
44
            x >>= 1;
45
        }
46
        return res;
47
    };
48
    for(int i = 0; i < (1<<n); ++i){
49
        int cur = cal(i) + 1;
50
        for(int j = 0; j < n; ++j){
51
            if((i>>j)&1)    continue;
52
            dp[i|1<<j] = min(dp[i|1<<j], dp[i] + a[j+1][cur]);
53
        }
54
    }
55
    cout << dp[(1<<n)-1] << endl;
56
    return 0;
57
}

第二题#

方法一#

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef pair<int, int > pii;
5
inline ll qpow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res = (res*a)%mod;a=(a*a)%mod;b>>=1;}return res;}
6
const int mod = 1e9 + 7;
7
const int MAXN = 2e5 + 7;
8

9
int t[16], g[16];
10
int dp[226][1<<15][3];
11
int main(){
12
    #ifndef ONLINE_JUDGE
13
        freopen("in.txt", "r", stdin);
14
        freopen("out.txt", "w", stdout);
15
    #endif
16

17
    int n, m;
18
    cin >> n >> m;
19
    for(int i = 1; i <= n; ++i){
20
        cin >> t[i] >> g[i];
21
        g[i]--;
22
    }
23
    dp[0][0][0] = 1;
24
    dp[0][0][1] = 1;
25
    dp[0][0][2] = 1;
26
    for(int i = 0; i <= m; ++i){
27
        for(int j = 0; j < (1<<n); ++j){
28
            for(int k = 0; k < n; ++k){
29
                if((j>>k)&1)    continue;
30
                if(i+t[k+1] > m)    continue;
31
                for(int type = 0; type < 3; ++type){
32
                    if(type == g[k+1])    continue;
33
                    // cout << i+t[k+1] << ' ' << (j|1<<k) << ' ' << g[k+1] << endl;
34
                    dp[i+t[k+1]][j|1<<k][g[k+1]] += dp[i][j][type];
35
                    dp[i+t[k+1]][j|1<<k][g[k+1]] %= mod;
36
                }
37
            }
38
        }
39
    }
40
    ll res = 0;
41
    for(int i = 0; i < (1<<n); ++i){
42
        for(int j = 0; j < 3; ++j){
43
            res += dp[m][i][j];
44
            res %= mod;
45
        }
46
    }
47
    cout << res*qpow(2, mod-2, mod)%mod << endl;
48
    return 0;
49
}

方法二#

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef pair<int, int > pii;
5
inline ll qpow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res = (res*a)%mod;a=(a*a)%mod;b>>=1;}return res;}
6
const int mod = 1e9 + 7;
7
const int MAXN = 2e5 + 7;
8

9
int t[16], g[16];
10
int dp[1<<16][3];
11
int main(){
12
    #ifndef ONLINE_JUDGE
13
        freopen("in.txt", "r", stdin);
14
        freopen("out.txt", "w", stdout);
15
    #endif
16

17
    int n, m;
18
    cin >> n >> m;
19
    for(int i = 1; i <= n; ++i){
20
        cin >> t[i] >> g[i];
21
    }
22
    dp[0][1] = dp[0][2] = dp[0][3] = 1;
23
    for(int i = 0; i < (1<<n); ++i){
24
        for(int j = 0; j < n; ++j){
25
            if((i>>j)&1)    continue;
26
            for(int k = 1; k <= 3; ++k){
27
                if(k == g[j+1]) continue;
28
                dp[i|1<<j][g[j+1]] += dp[i][k];
29
                dp[i|1<<j][g[j+1]] %= mod;
30
            }
31
        }
32
    }
33
    ll res = 0;
34
    for(int i = 0; i < (1<<n); ++i){
35
        for(int j = 1; j <= 3; ++j){
36
            int tmp = 0;
37
            for(int k = 0; k < n; ++k){
38
                if((i>>k)&1){
39
                    tmp += t[k+1];
40
                }
41
            }
42
            if(tmp == m){
43
                res += dp[i][j];
44
                res %= mod;
45
            }
46
        }
47
    }
48
    cout << res*qpow(2, mod-2, mod)%mod << endl;
49
    return 0;
50
}