POJ 3267 The Cow Lexicon
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 7909 | Accepted: 3711 |
Description
Few know that the cows have their own dictionary with W (1 ≤ W ≤ 600) words, each containing no more 25 of the characters 'a'..'z'. Their cowmunication system, based on mooing, is not very accurate; sometimes they hear words that do not make any sense. For instance, Bessie once received a message that said "browndcodw". As it turns out, the intended message was "browncow" and the two letter "d"s were noise from other parts of the barnyard.
The cows want you to help them decipher a received message (also containing only characters in the range 'a'..'z') of length L (2 ≤ L ≤ 300) characters that is a bit garbled. In particular, they know that the message has some extra letters, and they want you to determine the smallest number of letters that must be removed to make the message a sequence of words from the dictionary.
Input
Line 2: L characters (followed by a newline, of course): the received message
Lines 3..W+2: The cows' dictionary, one word per line
Output
Sample Input
6 10 browndcodw cow milk white black brown farmer
Sample Output
2
题意:怎样删除最少的字母,可以使得字符串是以下列出来的字符串的连接。
动态规划,这里是从前往后的DP方程。
AC代码例如以下:
#include<iostream> #include<cstring> #include<algorithm> using namespace std; int min(int a,int b) { return a<b?a:b; } int main() { int n,m; int i,j; char a[610],b[1005][1005]; int dp[610]; int la,lb; int x,y; while(cin>>n>>m) { cin>>a+1; for(i=0;i<n;i++) cin>>b[i]+1; dp[0]=0; for(i=1;i<=m;i++) { dp[i]=dp[i-1]+1;//假设无法匹配 for(j=0;j<n;j++) { lb=strlen(b[j]+1); x=0;y=lb; if(i>=lb&&a[i]==b[j][lb]) { while(i-x>0) { if(a[i-x]==b[j][y]) {x++;y--;} else x++; if(!y) { dp[i]=min(dp[i],dp[i-x]+x-lb); break; } } } } } cout<<dp[m]<<endl; } return 0; }
相关文章
- Scalaz(9)- typeclass:checking instance abiding the laws
- SQL SERVER 2005删除维护作业报错:The DELETE statement conflicted with the REFERENCE constraint "FK_subplan_job_id"
- [RxJS 6] The Catch and Rethrow RxJs Error Handling Strategy and the finalize Operator
- About the Mean Shift
- [React] Use the Fragment Short Syntax in Create React App 2.0
- [Angular2 Form] Understand the Angular 2 States of Inputs: Pristine and Untouched
- The CPU Costing Model: A Few Thoughts Part IV (Map of the Problematique)
- Mark task complete in checkbox S2 Resource not found for the segment Tasks
- How to handle the generic error Cannot read property md of undefined
- 【56.74%】【codeforces 732B】Cormen --- The Best Friend Of a Man
- 成功解决ValueError: The truth value of a Series is ambiguous. Use a.empty, a.bool(), a.item(), a.any() o
- Unexpected XML declaration. The XML declaration must be the first node in the document and no white
- NLP:LSTM之父眼中的深度学习十年简史《The 2010s: Our Decade of Deep Learning / Outlook on the 2020s》的参考文献
- 成功解决404 Not Found Not Found The requested URL was not found on the server. If yo
- The encryption certificate of the relying party trust identified by thumbprint is not valid
- 论文解读(SR-GNN)《Shift-Robust GNNs: Overcoming the Limitations of Localized Graph Training Data》
- POJ 2965:The Pilots Brothers' refrigerator
- POJ 2567 Code the Tree & POJ 2568 Decode the Tree Prufer序列
- 【大数据开发运维解决方案】记一次同事不慎用root起动weblogic以及启动日志卡在The server started in RUNNING mode 问题解决过程
- Error:The supplied javaHome seems to be invalid. I cannot find the java executable. Tried location:
- The value for the useBean class attribute is invalid.
- 存在隐患 : 3 racks are required for the erasure coding policies: RS-6-3-1024k. The number of racks is on
- Accidental override: The following declarations have the same JVM signature (getWindow()Landroid/vie