解題區/解題區 - UVa

UVa 10999 - Crabbles

contents

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

Problem

有 N 個單詞，現在有 M 張字卡，字卡上有各自的字母、權重。挑選字卡出來排列，若剛好拼出 N 個單詞中的一個，則得分為挑選字卡的權重總和。給定數場不同的字卡集，對於每一場請問最多能獲得多少分。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
abcd
hgfe
1
10
a 1
b 2
c 3
d 4
e 5
f 6
g 7
h 8
i 9
j 10

Sample Output

1
26

Solution

由於 N 非常大，M 非常小，詢問次數非常多。

每次窮舉單詞來進行最大權匹配相當浪費時間，每個詢問是 $O(N)$ 次窮舉。因此考慮窮舉挑選的字卡，接著在快速的時間 $O(2^M)$內進行單詞查找。

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <map>
#include <algorithm>
#define MAXCHAR 26 
#define MAXS (4096)
#define MAXNODE (1048576<<2)
#pragma comment( linker, "/STACK:1024000000,1024000000")
using namespace std;
class Trie {
public:
    struct Node {
        Node *next[MAXCHAR];
        int cnt;
        void init() {
            cnt = 0;
            memset(next, 0, sizeof(next));
        }
    } nodes[MAXNODE];
    Node *root;
    int size, cases;
    Node* getNode() {
        Node *p = &nodes[size++];
        p->init();
        return p;
    }
    void init() {
        size = cases = 0;
        root = getNode();
    }
    inline int toIndex(char c) {
        return c - 'a';
    }
    // merge trie
    void merge_dfs(Node *p, Node *q) {
        for (int i = 0; i < MAXCHAR; i++) {
            if (q->next[i]) {
                Node *u = p->next[i], *v = q->next[i];
                if (u == NULL)
                    p->next[i] = getNode(), u = p->next[i];
                u->cnt += v->cnt;
                merge_dfs(u, v);
            }
        }
    }
    void merge(const Trie &other) {
        merge_dfs(root, other.root);
    }
    // basis operation
    void insert(const char str[], int w) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        p->cnt += w;
    }
    int find(const char str[]) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        return p->cnt;
    }
        
    void free() {
        return ;
        // owner memory pool version
        queue<Node*> Q;
        Q.push(root);
        Node *u;
        while (!Q.empty()) {
            u = Q.front(), Q.pop();
            for (int i = 0; i < MAXCHAR; i++) {
                if (u->next[i] != NULL) {
                    Q.push(u->next[i]);
                }
            }
            delete u;
        }
    }
} tool;
char S[MAXS], buf[MAXS];
int main() {
    int n, m, q;
    while (scanf("%d", &n) == 1) {
        tool.init();
        for (int i = 0; i < n; i++) {
            scanf("%s", S);
            int m = strlen(S);
            sort(S, S+m);
            tool.insert(S, 1);
        }
        
        scanf("%d", &q);
        for (int i = 0; i < q; i++) {
            scanf("%d", &m);
            
            char letter[26][2];
            int val[26];
            for (int j = 0; j < m; j++)
                scanf("%s %d", letter[j], &val[j]);
                
            // brute
            int max_score = 0;
            for (int j = (1<<m)-1; j >= 0; j--) {
                int idx = 0, sum = 0;
                for (int k = 0; k < m; k++) {
                    if ((j>>k)&1) 
                        buf[idx++] = letter[k][0], sum += val[k];
                }
                buf[idx] = '\0';
                sort(buf, buf + idx);
                if (tool.find(buf))
                    max_score = max(max_score, sum);
            }
            printf("%d\n", max_score);
        }
        tool.free();    
    }
    return 0;
}
/*
 */