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

The 2007 ACM Northwestern European Programming Contest

題目意思，將一個句子的單字首尾不動，單字中間字母打亂，然後把空白去掉。
然後給你一些會用到的單字，問解讀方法，單字可以重複用的。

很明顯地，會發現是個 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;
}

我要檢舉

#12131#Obfuscation

台長： Morris

您可能對以下文章有興趣

[UVA][dp][最優二叉樹] 12057 - Prefix Codes

[UVA][字串處理] 11278 - One-Handed Typist

[UVA] 11332 - Summing Digits

[UVA] 112 - Tree Summing

人氣(577) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][多邊形] 11473 - Campus Roads
此分類上一篇:[UVA] 1419 - Ugly Windows

回應(0)