UVA - 1204 Fun Game——状压dp

UVA - 1204 Fun Game——状压dp

题意：

给定n个串（n<=16），要求一个最短的环，使得每个串都是这个环的子串，输出环的长度。

思路：

定义dp（i，j，k）为状态（选定的串的集合， 最后一个串的下标，最后一个串的接法（0正接1反接））的最大重合长度

初始化：

dp（1,0,0）=0；

因为题目要求的是环，所以我们一开始要任意选一个串作为环的开头，这里我选择的是下标为0的字符串，并且正放

转移方程：

dp(i|(1<

转移上是状压dp的基本套路，表示状态（i，j，k）转移到状态（i|(1<

cover（j，t，k，p）表示下标为j的串s【j】和下标为t的串s【t】的重合长度，k表示s【j】正放/反放，p表示s【t】正放/反放

结果：

ans = min(ans, sum - dp(1<

sum表示所有串的总长度，结果就是总长度减去最大重合长度，注意因为是环，所以要考虑最后一个串和第一个串重合的情况，所以还要减去cover(i, 0, j, 0)

dp方面就到这里了，以下才是这道题的恶心之处：

预处理：

根据上述的dp过程我们需要预处理cover，但在这之前我们需要去除完全包含在另一个串的那些串，当个模拟做就好了

#include #include #include #include #include using namespace std;const int maxn = 20;const int maxm = 110;int n;string temp[maxn], s[maxn];bool vis[maxn];int cover[maxn][maxn][2][2];int sum, dp[(1<<16)+10][maxn][2];string rev(string s1) { int len = s1.size(); for (int i = 0, j = len-1; i < j; i++, j--) swap(s1[i], s1[j]); return s1;}bool judge(string s1, string s2) { for (unsigned int k = 0; k < s2.size(); k++) { bool flag = true; for (unsigned int t = 0; t < s1.size(); t++) { if (k + t >= s2.size() || s1[t] != s2[k+t]) { flag = false; break; } } if (flag) return true; } return false;}void init1() { memset(vis, false, sizeof(vis)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (j == i || vis[j]) continue; if (judge(temp[i], temp[j]) || judge(rev(temp[i]), temp[j])) { vis[i] = true; break; } } } sum = 0; int cnt = 0; for (int i = 0; i < n; i++) { if (!vis[i]) { sum += temp[i].size(); s[cnt++] = temp[i]; } } n = cnt;}int cal(string s1, string s2) { for (unsigned int i = 1; i < s1.size(); i++) { bool flag = true; for (unsigned j = 0; j < s2.size() && i + j < s1.size(); j++) { if (s1[i+j] != s2[j]) { flag = false; break; } } if (flag) return s1.size() - i; } return 0;}void init2() { memset(cover, 0, sizeof(cover)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cover[i][j][0][0] = cal(s[i], s[j]); cover[i][j][0][1] = cal(s[i], rev(s[j])); cover[i][j][1][0] = cal(rev(s[i]), s[j]); cover[i][j][1][1] = cal(rev(s[i]), rev(s[j])); } }}int main() { while (~scanf("%d", &n) && n) { for (int i = 0; i < n; i++) cin >> temp[i]; init1(); init2(); memset(dp, -1, sizeof(dp)); dp[1][0][0] = 0; for (int i = 1; i < (1<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。