pku 3267 The Cow Lexicon

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

\#include <iostream> \#include <string> 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 <iostream> \#include <string> 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; \} \*/