Codeforces Round 961 D. Cases 【SOS DP、思维】

D. Cases

题意

有一个长度为 $n$ 且仅由前 $c$ 个大写字母组成的字符串，问最少选取多少种字母为每个单词的结尾，使得每个单词长度不超过 $k$

思路

首先注意到最后一个字母一定要选择，接下来我们给出一个断言：如果一个字母被选上了，那么对于这个字母在字符串中所有出现的位置，用这些位置作为结尾是最优的
这是因为如果最优的答案存在一个单词横跨了所选的这个字母，因为这个单词长度本身小于等于 $k$，所以我们把他划分成两段，一段以所选的字母结尾，另一段以原先单词自己的字母结尾，这样子并不会使得答案更劣，所以我们一旦选择了某个字母，一定是选择其在字符串中出现的所有位置

进一步观察发现：对于每 $k$ 个连续的字符，我们一定至少选择 $1$ 个字母作为结尾
简化一下单词长度不超过 $k$ 的这个条件，我们如果对于每一个长度恰好为 $k$ 的一个窗口，把这个窗口里所有出现的字母记录一下，形成一个 $mask$，那么对于所有的 $O(n)$ 个 $mask$，我们等价于要满足每个 $mask$ 都至少有 $1$ 位被选作最终的答案集合

至此，问题便转化为了：对于 $O(n)$ 个 $mask$，我们要选择一个含 $1$ 数量最少的，且与每个 $mask$ 有交，且 $ans$ 必须包含最后一个字母

直接枚举 $ans$ 并与 $O(n)$ 个 $mask$ 求交太慢，我们可以先把全部不合法的 $ans$ 筛出来，再从剩下的所有合法的 $ans$ 中选一个最少的即可

接下来我们将 $O(n)$ 个 $mask$ 放入数组 $a$ 中，注意到一个答案 $b$ 如果不合法，那么一定有 $b\&a_i=0$，即一定存在至少一个 $mask$，使得 $b$ 与其没有任何的交集，那么这个 $b$ 不合法
剩下的一定是合法的。
注意到：$a\&b=0\iff b\subset \tilde{a}(a的补集)$，即 $b$ 是 $a$ 的补集的子集
现在我们有了 $O(n)$ 个母集 $a_i$，我们需要筛出其所有的子集 $b\subset a_i$，这个过程我们可以使用 $SOSDP$

时间复杂度：$O(cn+c{2}^c)$

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;const int INF=0x3f3f3f3f;
const long long INFLL=1e18;typedef long long ll;int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int t;std::cin >> t;while(t--){int n, c, k;std::cin >> n >> c >> k;std::string s;std::cin >> s;s = '0' + s;std::vector<std::vector<int>> sum(n + 1, std::vector<int>(26, 0));std::vector<int> a;fore(i, 1, n + 1){int ch = s[i] - 'A';fore(j, 0, c) sum[i][j] = sum[i - 1][j];++sum[i][ch];if(i >= k){int mask = 0;fore(j, 0, c)if(sum[i][j] - sum[i - k][j])mask |= 1 << j;a.push_back(mask);}}for(int& mask : a) mask = (~mask & ((1 << c) - 1));std::vector<int> dp(1 << c, 1);for(auto mask : a) dp[mask] = 0;fore(i, 0, c)fore(mask, 0, 1 << c)if(!(mask >> i & 1))dp[mask] &= dp[mask ^ (1 << i)];int last = s.back() - 'A';int ans = c;fore(mask, 0, 1 << c)if(dp[mask] && (mask >> last & 1))ans = std::min(ans, __builtin_popcount(mask));std::cout << ans << endl;}return 0;
}