原题链接:https://vjudge.net/problem/UVA-1204 分类:状压DP 备注:字符串覆盖
按紫书的思路,首先排除被覆盖的串,每个串都试着正反两个状态,与当前集合的最后一个串计算覆盖量,取最优。这里固定以某一个串为第一个串,就可以很方便地来把最后一个串和第一个串连起来。
注意有效串个数为1,以及长度小于等于1应该变为2的情况。
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
const int INF = 0x3f3f3f3f;
int n, len[N], cover[N][N][2][2], dp[1 << N][N][2];
string s[N][2];
struct String {
string s, rev;
bool operator < (const String& rhs) const {
return s.length() < rhs.s.length();
}
}input[N];
int calc(const string& a, const string& b) {
int len1 = a.length();
int len2 = b.length();
for (int i = 1; i < len1; i++) {
if (i + len2 < len1) continue;
int flg = 1;
for (int j = 0; i + j < len1; j++) {
if (a[i + j] != b[j]) {
flg = 0;
break;
}
}
if (flg) return len1 - i;
}
return 0;
}
int main(void) {
while(cin >> n && n) {
for (int i = 0; i < n; i++) {
cin >> input[i].s;
input[i].rev = input[i].s;
reverse(input[i].rev.begin(), input[i].rev.end());
}
sort(input, input + n);
int tot = 0, sumLen = 0;
for (int i = 0; i < n; i++) {
int covered = 0;
for (int j = i + 1; j < n; j++) {
if (input[j].s.find(input[i].s) != string::npos ||
input[j].s.find(input[i].rev) != string::npos) {
covered = 1;
break;
}
}
if (covered) continue;
s[tot][0] = input[i].s;
s[tot][1] = input[i].rev;
len[tot] = input[i].s.length();
sumLen += len[tot];
tot++;
}
for (int i = 0; i < tot; i++)
for (int j = 0; j < tot; j++)
for (int o1 = 0; o1 < 2; o1++)
for (int o2 = 0; o2 < 2; o2++)
cover[i][j][o1][o2] = calc(s[i][o1], s[j][o2]);
memset(dp, -1, sizeof(dp));
dp[1][0][0] = 0;
for (int sta = 1; sta < (1 << tot) - 1; sta++)
for (int e = 0; e < tot; e++)
for (int o = 0; o < 2; o++)
if (dp[sta][e][o] >= 0)
for (int j = 1; j < n; j++) {
if (sta & (1 << j)) continue;
for (int o2 = 0; o2 < 2; o2++)
dp[sta | (1 << j)][j][o2] = max(dp[sta | (1 << j)][j][o2], dp[sta][e][o] + cover[e][j][o][o2]);
}
int maxCover = 0, ans;
for (int i = 1; i < tot; i++)
for (int o = 0; o < 2; o++)
maxCover = max(maxCover, dp[(1 << tot) - 1][i][o] + cover[i][0][o][0]);
if (tot == 1) ans = len[0] - cover[0][0][0][0];
else ans = sumLen - maxCover;
cout << (ans <= 1 ? 2 : ans) << endl;
}
return 0;
}
|