pku 3267 The Cow Lexicon-蒲公英云

pku 3267 The Cow Lexicon

矫情吗；* 2022-08-10 11:49 81阅读 0赞

#include #include using namespace std; int v[302]; char s[600][27]; char word[302]; int len[600]; int N, L; int main() { scanf(“%d%d”, &N, &L); scanf(“%s”, &word); for(int i = 0; i < N; ++i) { scanf(“%s”, &s[i]); len[i] = strlen(s[i]); } v[0] = 1; for(int i = 0; i < N; ++i) if(len[i] == 1 && word[0] == s[i][0]) v[0] = 0; for(int i = 1; i < L; ++i) { int Min = v[i-1]+1; for(int j = 0; j < N; ++j) if(i+1 >= len[j] && s[j][len[j]-1] == word[i]) { int index = i-1; int pos = len[j]-2; while(index >= 0 && pos >= 0) { if(s[j][pos] == word[index]) pos—; index—; } if(pos < 0 && v[index] + i-index-len[j] < Min) Min = v[index] + i-index-len[j]; } v[i] = Min; } printf(“%d/n”, v[L-1]); return 0; } /* //Learned: 本题若从后往前按照每个单词进行匹配,效率会高很多很多. 下面的TLE的解法就是因为对每个num[k+1, i]进行每个单词的匹配,效率很低. YJS: for(int j = 0; j < N; ++j) vs for(int k = 0; k < i; ++k) && for(int i = 0; i < N; ++i) 状态转移方程为: v[i] = min{v[k], num[k+1, i]} Problem: 3267 User: xiaofengsheng Memory: 412K Time: 63MS Language: G++ Result: Accepted */ /*#include #include using namespace std; int v[302]; char s[600][27]; char word[302]; int len[600]; int N, L; //v[i] = min{v[k], num[k+1, i]} (-1 <= k <= i-1); inline int f(int m, int n) { int Min = 100000; bool flag = false; for(int i = 0; i < N; ++i) { int pos = 0; int index = m; while(index <= n && pos < len[i]) { if(s[i][pos] == word[index]) pos++; index++; } if(pos == len[i] && n-m+1-pos < Min) { Min =n-m+1-pos; flag = true; } } if(flag) return Min; else return n-m+1; } int main() { scanf(“%d%d”, &N, &L); scanf(“%s”, &word); for(int i = 0; i < N; ++i) { scanf(“%s”, &s[i]); len[i] = strlen(s[i]); } for(int i = 0; i < N; ++i) puts(s[i]); v[0] = 1; for(int i = 0; i < N; ++i) if(len[i] == 1 && word[0] == s[i][0]) v[0] = 0; for(int i = 1; i < L; ++i) { int Min = f(0, i); for(int k = 0; k < i; ++k) { int ret = f(k+1, i); if(v[k] + ret < Min) Min = v[k] + ret; } v[i] = Min; } printf(“%d/n”, v[L-1]); return 0; } */