#### HDU 2340 – Obfuscation [DP]

http://acm.hdu.edu.cn/showproblem.php?pid=2340

### Problem

It is a well-known fact that if you mix up the letters of a word, while leaving the first and last letters in their places, words still remain readable. For example, the sentence “tihs snetncee mkaes prfecet sesne”, makes perfect sense to most people.

If you remove all spaces from a sentence, it still remains perfectly readable, see for example: “thissentencemakesperfectsense”, however if you combine these two things, first shuffling, then removing spaces, things get hard. The following sentence is harder to decipher: “tihssnetnceemkaesprfecetsesne”.

You’re given a sentence in the last form, together with a dictionary of valid words and are asked to decipher the text.

### Analysis

dp需要记录路径。好多地方处理起来需要技巧，详见代码。

### Code

```#include <bits/stdc++.h>
using namespace std;

const int maxn = 1024;
int M, sz, maxlen;
int dp[maxn], id[maxn];
char str[maxn];
char v[maxn*10][105];
unordered_map<string, vector<int>> mp;

int solve(int L) {
if(L >= sz) return 1;
int &ans = dp[L];
if(ans != -1) return ans;
string tmp;
ans = 0;
for(int r = L; r < sz && r-L+1 <= maxlen; ++r) {
tmp.push_back(str[r]);
auto it = mp.find(tmp);
if(tmp.size() >= 2) {
tmp.pop_back();
tmp.insert(lower_bound(tmp.begin()+1, tmp.end(), str[r]), 1, str[r]);
}
if(it == mp.end()) continue;
int cur = it->second.size() * solve(r + 1);
ans += cur;
if(ans >= 2)
break;
if(cur) {
id[L] = it->second.front();
}
}
return ans;
}

int main() {
int T; scanf("%d", &T);
while(T--) {
scanf("%s%d", str, &M);
mp.clear();
maxlen = 0;
sz = strlen(str);
for(int i = 1; i <= M; ++i) {
scanf("%s", v[i]);
string cur(v[i]);
maxlen = max(maxlen, (int)cur.size());
if(cur.size() > 2)
sort(cur.begin() + 1, cur.end() - 1);
mp[cur].push_back(i);
}
memset(dp, -1, sizeof(dp));
int ans = solve(0);
if(ans >= 2) puts("ambiguous");
else if(ans <= 0) puts("impossible");
else {
vector<int> out;
int L = 0;
while(L < sz) {
out.push_back(id[L]);
L += strlen(v[id[L]]);
}
for(int i = 0; i < out.size(); ++i)
printf("%s%c", v[out[i]], i==out.size()-1 ? '\n' : ' ');
}
}
return 0;
}
```