[UVA][dp] 12131 - Obfuscation
Problem H - Obfuscation
Time limit: 5 seconds
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 decypher: ``tihssnetnceemkaesprfecetsesne''.
You're given a sentence in the last form, together with a dictionary of valid words and are asked to decypher the text.
Input
On the first line one positive number: the number of testcases, at most 100. After that per testcase:
- One line with a string s: the sentence to decypher. The sentence consists of lowercase letters and has a length of at least 1 and at most 1000 characters.
- One line with an integer n with 1 ≤ n ≤ 10000: the number of words in the dictionary.
- n lines with one word each. A word consists of lowercase letters and has a length of at least 1 and at most 100 characters. All the words are unique.
Output
Per testcase:
- One line with the decyphered sentence, if it is possible to uniquely decypher it. Otherwise ``impossible'' or ``ambiguous'', depending on which is the case.
Sample Input
3 tihssnetnceemkaesprfecetsesne 5 makes perfect sense sentence this hitehre 2 there hello hitehre 3 hi there three
Sample Output
this sentence makes perfect sense impossible ambiguous
題目意思，將一個句子的單字首尾不動，單字中間字母打亂，然後把空白去掉。
然後給你一些會用到的單字，問解讀方法，單字可以重複用的。
很明顯地，會發現是個 dp 問題，
dp[i] 代表 [0,i-1] 的解讀方法數，然後疊加一個長度為 j 的字串，
就可以得到 dp[i+j] 的方法數，意即 dp[i+j] += dp[i];
#include <stdio.h>
#include <map>
#include <algorithm>
#include <iostream>
#include <string.h>
using namespace std;
char s[1005], word[10005][105];
struct E {
int v, idx;
};
int main() {
int t, n, i, j, k;
scanf("%d", &t);
while(t--) {
scanf("%s", s);
scanf("%d", &n);
map<string, E> W;
map<string, E>::iterator it;
for(i = 0; i < n; i++) {
scanf("%s", word[i]);
string tmp(word[i]);
sort(tmp.begin(), tmp.end());
tmp = tmp + word[i][0] + word[i][strlen(word[i])-1];
it = W.find(tmp);
if(it == W.end())
W[tmp].v = 1, W[tmp].idx = i;
else
W[tmp].v++;
}
int dp[1505] = {}, m = strlen(s);
int arg_dp[1505][2] = {};
dp[0] = 1;
for(i = 0; i < m; i++) {
if(dp[i])
for(j = 1; j < 105 && i+j <= m; j++) {
char tmp = s[i+j];
s[i+j] = '\0';
string buf(s+i);
sort(buf.begin(), buf.end());
buf = buf + s[i] + s[i+j-1];
it = W.find(buf);
if(it != W.end()) {
dp[i+j] += dp[i]*(it->second.v);
if(dp[i+j] > 2) dp[i+j] = 2;
arg_dp[i+j][0] = i;
arg_dp[i+j][1] = it->second.idx;
}
s[i+j] = tmp;
}
}
if(dp[m] == 0)
puts("impossible");
else if(dp[m] == 2)
puts("ambiguous");
else {
int buf[10005];
int bidx = 0;
while(m) {
buf[bidx++] = arg_dp[m][1];
m = arg_dp[m][0];
}
printf("%s", word[buf[bidx-1]]);
for(i = bidx-2; i >= 0; i--)
printf(" %s", word[buf[i]]);
puts("");
}
}
return 0;
}