[一本通1683]稗田阿求（一本通高手训练-1683）

有句话说得好 记忆化搜索=动态规划

训练的时候看了：< (cnblogs.com)>

不过我觉得不需要状态压缩，用更好理解的方法写代码。

转移方式一：

如果加入这一组，那就需要这一组满足前面的对应关系。并加上这一组所带来的对应关系。

转移方式二：

不加入这一组。

直接上代码，有注释的。

 1 // ZZQF5677 | 20241004
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 long long n, m;
 5 // 对于每一组可选也可以不选。
 6 struct Node {
 7     string s;
 8     long long len;
 9     long long a[255]; // 每个数字对应的字母。 
10     long long zm[255]; // 每个字母对应的数字。 
11 } C[255];
12 long long ans = 0;
13 long long k[255]; /*k[i]=j 数字 i 对应字母 j*/
14 long long l[255]; /*l[i]=j 字母 i 对应数字 j*/
15 void dfs(long long step/*处理到第几个*/, long long num/*当前可行的组数*/) {
16     if (step > m) {
17         ans = max(ans, num);
18         return ;
19     }
20     if (num + m - step + 1 < ans) {
21         return ;
22     }    
23     // 选这一个：
24     //step++; // 一定要注意：这里处理的是下一个状态。 
25     bool f = 1;
26     for (long long i = 1; i <= C[step].len; i++) {
27         if (k[C[step].a[i]] != 0 && k[C[step].a[i]] != C[step].s[i]) {
28             f = 0;
29             break;
30         }
31         if (l[C[step].s[i] - 'A' + 1] != 0 && l[C[step].s[i] - 'A' + 1] != C[step].a[i]) {
32             f = 0;
33             break;
34         }
35     } 
36     // 注意一定不能有一个字母对应多个数字。 
37     if (f) {
38         queue<long long> q;
39         while (!q.empty()) {
40             q.pop();
41         }
42         queue<long long> zzz;
43         while (!zzz.empty()) {
44             zzz.pop();
45         }        
46         for (long long i = 1; i <= C[step].len; i++) {
47             if (k[C[step].a[i]] == 0) {
48                 q.push(C[step].a[i]);
49                 k[C[step].a[i]] = C[step].s[i];
50             }
51             if (l[C[step/*记得这里变量打错了！！！*/].s[i] - 'A' + 1] == 0) {
52                 zzz.push(C[step].s[i] - 'A' + 1);
53                 l[C[step].s[i] - 'A' + 1] = C[step].a[i];
54             }
55         }        
56         dfs(step + 1, num + 1);
57         while (!q.empty()) {
58             k[q.front()] = 0;
59             q.pop();
60         }        
61         while (!zzz.empty()) {
62             l[zzz.front()] = 0;
63             zzz.pop();
64         }        
65     }    
66     // 不选这一个： 
67     dfs(step + 1, num);
68     return ;
69 }
70 // 剪枝。 
71 // 当已经赋值了的数字个数、每个数字对应情况相同的时候，选择答案大的。（数据太水了，就不用了。。。。。。） 
72 // 后面的都加上，都比答案小的，删掉。
73 int main() {
74     cin >> n >> m;
75     for (long long i = 1; i <= m; i++) {
76         cin >> C[i].s;
77         C[i].len = C[i].s.size();
78         C[i].s = " " + C[i].s;
79         for (long long j = 1; j <= C[i].len; j++) {
80             cin >> C[i].a[j];
81         }
82     }
83     dfs(1, 0);
84     //dfs(0, op);
85     cout << ans << "\n";
86     return 0;
87 }
88 
89 /*
90 5 3
91 ABCDE
92 1 2 3 4 5
93 AAAAA
94 5 5 5 5 5
95 CCAAA
96 2 2 1 1 1
97 
98 */