HDU 2340 – Obfuscation [DP]

Link

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.

Mean

给定一个句子,在每个单词中,打乱除首尾处内部字母的顺序,然后再把单词间空格去掉连接起来。给定这些单词的一个词典和打乱+连接后的句子,问你能否还原出唯一的原句子。

Analysis

集训队个人赛的题目…看错题了…非常自信的写出了算法然后卡了三个小时…哎….

设dp[i]为str[i:len]子串中能够凑成的方案数,其实只有三种状态:dp[i]=0(无法凑出),dp[i]=1(唯一凑出),dp[i]=2(多重方案)。

转移的话,dp[i] = sum(dp[j]*ss[i:j]),ss[i:j]代表子串str[i:j]能够代表几种单词。

这样的话,关键就在判断str[i:j]能够被几个单词代表。我们可以把给定的词典单词的中间字母排序,然后放在map里,这样边dp边构造查询串在map直接查询就好。

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;
}

欢迎留言