首页 > 代码库 > HDU 2340 - Obfuscation（dp）
HDU 2340 - Obfuscation（dp）
题意：一个句子中有多个单词，但是目前的单词，除了首末两位，中间的单词字母顺序均被打乱，并且打乱后把单词间的空格删掉变成一个新句子。现在给定这个新句子（长度为1~1000），给定n个单词（1 <= n <= 10000），且每个单词是唯一的，求是否能用这n个单词还原出这个句子的原来的样子，若不能则输出"impossible"，若多解则输出"ambiguous"，否则输出这个句子。（例：tihssnetnceemkaesprfecetsesne，给定makes，perfect，sense，sentence，this，只有一种解读方式：this sentence makes perfect sense）
1、d[i]表示从开始到第 i 位这一段有几种构成方法；
2、从前往后找，看看对于某一位能不能往前延伸构成一个单词，设 i ~ j 位可以构成一个单词，则 d[j] += d[i - 1]，最后看d[len - 1]的情况即可；
3、对于每个单词记录前缀和后缀，以及，记录每个单词的字母个数和目标串截止到每一位的字母个数，方便减小枚举量；
4、边dp边记录达到状态转移的要求的某一位的来源。
总共两个AC代码，第一次900ms多差点超时，换种写法写之后只有62ms，还是能用char数组就用char数组表示字符串，string太浪费时间。
代码如下：
62ms
#include<cstdio> #include<cstring> #include<cctype> #include<cstdlib> #include<cmath> #include<iostream> #include<sstream> #include<iterator> #include<algorithm> #include<string> #include<vector> #include<set> #include<map> #include<deque> #include<queue> #include<stack> #include<list> #define fin freopen("in.txt", "r", stdin) #define fout freopen("out.txt", "w", stdout) #define pr(x) cout << #x << " : " << x << " " #define prln(x) cout << #x << " : " << x << endl #define Min(a, b) a < b ? a : b #define Max(a, b) a < b ? b : a typedef long long ll; typedef unsigned long long llu; const int INT_INF = 0x3f3f3f3f; const int INT_M_INF = 0x7f7f7f7f; const ll LL_INF = 0x3f3f3f3f3f3f3f3f; const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f; const double pi = acos(-1.0); const double EPS = 1e-6; const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1}; const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1}; const ll MOD = 1e9 + 7; using namespace std; #define NDEBUG #include<cassert> const int MAXN = 1000 + 10; const int MAXT = 10000 + 10; char s[MAXT][110]; struct Node{ int id, len, num[30]; char head; Node(int ids, int le) : id(ids), len(le){ memset(num, 0, sizeof num); for(int i = 0; i < len; ++i) ++num[s[id][i] - ‘a‘]; head = s[id][0]; } }; int T, n, plen, d[MAXN], last[MAXN], thisidx[MAXN], thisidy[MAXN], o[MAXN][30]; char p[MAXN]; vector<Node> vec[30]; inline bool judge(Node &u, int l, int r){ if(l == 0){ for(int i = 0; i < 26; ++i) if(u.num[i] != o[r][i]) return false; return true; } else{ for(int i = 0; i < 26; ++i) if(u.num[i] != o[r][i] - o[l - 1][i]) return false; return true; } } void init(){ for(int i = 0; i < 26; ++i) vec[i].clear(); memset(d, 0, sizeof d); memset(thisidy, 0, sizeof thisidx); memset(thisidx, 0, sizeof thisidy); memset(last, -1, sizeof last); memset(o[0], 0, sizeof o[0]); ++o[0][p[0] - ‘a‘]; for(int i = 1; i < plen; ++i){ for(int j = 0; j < 26; ++j) o[i][j] = o[i - 1][j]; ++o[i][p[i] - ‘a‘]; } } int main(){ scanf("%d", &T); while(T--){ scanf("%s", p); plen = strlen(p); init(); scanf("%d", &n); for(int i = 0; i < n; ++i){ scanf("%s", s[i]); int le = strlen(s[i]); vec[s[i][le - 1] - ‘a‘].push_back(Node(i, le)); } for(int i = 0; i < plen; ++i){ int lur = p[i] - ‘a‘; for(int j = 0; j < vec[lur].size(); ++j){ Node &u = vec[lur][j]; int tmp = i - u.len + 1; if(tmp == 0 && u.head == p[tmp] && judge(u, tmp, i)){ ++d[i]; thisidx[i] = lur; thisidy[i] = j; } else if(tmp > 0 && u.head == p[tmp] && judge(u, tmp, i) && d[tmp - 1]){ d[i] += d[tmp - 1]; last[i] = tmp - 1; thisidx[i] = lur; thisidy[i] = j; } } } if(!d[plen - 1]) printf("impossible\n"); else if(d[plen - 1] > 1) printf("ambiguous\n"); else{ bool flag = false; stack<pair<int, int> > st; for(int i = plen - 1; i != -1; i = last[i]) st.push(pair<int, int>(thisidx[i], thisidy[i])); while(!st.empty()){ if(flag) printf(" "); pair<int, int> tmp = st.top(); st.pop(); printf("%s", s[vec[tmp.first][tmp.second].id]); flag = true; } printf("\n"); } } return 0; }
967ms
#include<cstdio> #include<cstring> #include<cctype> #include<cstdlib> #include<cmath> #include<iostream> #include<sstream> #include<iterator> #include<algorithm> #include<string> #include<vector> #include<set> #include<map> #include<deque> #include<queue> #include<stack> #include<list> #define fin freopen("in.txt", "r", stdin) #define fout freopen("out.txt", "w", stdout) #define pr(x) cout << #x << " : " << x << " " #define prln(x) cout << #x << " : " << x << endl #define Min(a, b) a < b ? a : b #define Max(a, b) a < b ? b : a typedef long long ll; typedef unsigned long long llu; const int INT_INF = 0x3f3f3f3f; const int INT_M_INF = 0x7f7f7f7f; const ll LL_INF = 0x3f3f3f3f3f3f3f3f; const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f; const double pi = acos(-1.0); const double EPS = 1e-6; const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1}; const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1}; const ll MOD = 1e9 + 7; using namespace std; #define NDEBUG #include<cassert> const int MAXN = 1000 + 10; const int MAXT = 10000 + 10; struct Node{ string aftersort; int id, len; char head; Node(string &s, int ids){ id = ids; len = s.length(); aftersort = s; if(len > 3) sort(aftersort.begin() + 1, aftersort.end() - 1); head = aftersort[0]; } }; int T, n, plen, d[MAXN], last[MAXN], thisidx[MAXN], thisidy[MAXN]; string s[MAXT], p; vector<Node> vec[30]; inline bool judge(Node &u, int i){ string tmp = p.substr(i, u.len); if(u.len >= 3) sort(tmp.begin() + 1, tmp.end() - 1); return tmp == u.aftersort; } void init(){ for(int i = 0; i < 26; ++i) vec[i].clear(); memset(d, 0, sizeof d); memset(thisidy, 0, sizeof thisidx); memset(thisidx, 0, sizeof thisidy); memset(last, -1, sizeof last); } int main(){ scanf("%d", &T); while(T--){ init(); cin >> p; plen = p.length(); scanf("%d", &n); for(int i = 0; i < n; ++i){ cin >> s[i]; vec[*s[i].rbegin() - ‘a‘].push_back(Node(s[i], i)); } for(int i = 0; i < plen; ++i){ int lur = p[i] - ‘a‘; for(int j = 0; j < vec[lur].size(); ++j){ Node &u = vec[lur][j]; int tmp = i - u.len + 1; if(tmp == 0 && u.head == p[tmp] && judge(u, tmp)){ ++d[i]; thisidx[i] = lur; thisidy[i] = j; } else if(tmp > 0 && u.head == p[tmp] && judge(u, tmp) && d[tmp - 1]){ d[i] += d[tmp - 1]; last[i] = tmp - 1; thisidx[i] = lur; thisidy[i] = j; } } } if(!d[plen - 1]) printf("impossible\n"); else if(d[plen - 1] > 1) printf("ambiguous\n"); else{ bool flag = false; stack<pair<int, int> > st; for(int i = plen - 1; i != -1; i = last[i]) st.push(pair<int, int>(thisidx[i], thisidy[i])); while(!st.empty()){ if(flag) printf(" "); pair<int, int> tmp = st.top(); st.pop(); printf("%s", s[vec[tmp.first][tmp.second].id].c_str()); flag = true; } printf("\n"); } } return 0; }
HDU 2340 - Obfuscation（dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。