解題區/解題區 - UVa

UVa 11903 - e-Friends

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

N 個小夥伴排隊，每一個人都有不想排在某些人後面 (直接排在這個人之後)，對於一個排列將會統計有多少不滿意程度，不滿意程度即為排在他討厭的人後會得到 K 的總和。

詢問數次當不滿意程度小於等於 Q 的排列方法數。

Sample Input

1
2
3
4
5
6
1
2 10 2
1 2
0
10
5

Sample Output

1
2
3
Case 1:
2
1

Solution

每個人的不滿意程度都相同，化成單位 1，那麼不滿意總和最多為 N。

預處理 dp[state][last][K] 表示當前排列的人 state、最後一個人的編號 last、當前的不滿意總和 K，進行轉移即可。

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int dp[1<<12][12][12]; // dp[state][last][K] = ways
int main() {
    int testcase, cases = 0;
    int N, K, Q;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &N, &K, &Q);
        int em[16] = {};
        for (int i = 0; i < N; i++) {
            int t, x;
            scanf("%d", &t);
            for (int j = 0; j < t; j++) {
                scanf("%d", &x), x--;
                em[i] |= 1<<x;
            }
        }
        
        vector< pair<int, int> > A;
        for (int i = 0; i < (1<<N); i++)
            A.push_back(make_pair(__builtin_popcount(i), i));
        sort(A.begin(), A.end());
        
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < N; i++)
            dp[1<<i][i][0] = 1;
            
        for (int p = 0; p < A.size(); p++) {
            int s = A[p].second, t = A[p].first;
            for (int i = 0; i < N; i++) { // last
                for (int j = 0; j < t; j++) { // dissatisfaction index
                    if (dp[s][i][j] == 0)
                        continue;
//					printf("%d %d %d - %d\n", s, i, j, dp[s][i][j]);
                    for (int k = 0; k < N; k++) {
                        if ((s>>k)&1)	
                            continue;
                        int tt = j;
                        if ((1<<i)&em[k])	tt++;
                        dp[s|(1<<k)][k][tt] += dp[s][i][j];
                    }
                }
            }
        }
        
        int preCalc[16] = {};
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                preCalc[j] += dp[(1<<N)-1][i][j];
            }
        }
        
        printf("Case %d:\n", ++cases);
        for (int i = 0; i < Q; i++) {
            int x, ret = 0;
            scanf("%d", &x);
            if (K == 0)	x = N;
            else		x /= K;
            for (int j = 0; j <= x && j <= N; j++)
                ret += preCalc[j];
            printf("%d\n", ret);
        }
    }
    return 0;
}
/*
2
5 50 3
2 2 4
2 1 5
1 1
1 5
1 3
60
10
20
2 10 2
1 2
0
10
5
*/