大致题意:
给出一个长度为l的文本和一个由n个单词组成的字典。求至少从文本中去掉多少个字符才能使得这个文本全部由字典中的单词组成。
大致思路:
DP,转移方程为dp[i]=min(dp[i-1]+1,dp[pos+1]+i-pos-1-tmp);//dp[i]为前i个字符中需要去掉的字符数量。
转移的示例如下,这里文本是browndcodw 文本是cow,从str[9]开始匹配~~
b r o w n d c o d w
c o w //找到一个匹配,并需要剔除一个字母。所以dp[10]可以从dp[6]转化而来。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char str[1000];
char word[1000][30];
int dp[1000];
int main(){
int n,len,i,j,pos,k,tmp;
while(scanf("%d%d",&n,&len)!=EOF){
scanf("%s",str);
for(i=0;i<n;i++){
scanf("%s",word[i]);
}
dp[0]=0; //前i个字符中包含的非法字符数量
for(i=1;i<=len;i++){
dp[i]=dp[i-1]+1;
for(j=0;j<n;j++){
tmp=k=strlen(word[j]);
k-=1;
pos=i-1;
while(pos>=0&&k>=0){
if(str[pos]==word[j][k]){
k--;
}
pos--;
}
if(k<0){ //可以匹配出一个单词
dp[i]=min(dp[i],dp[pos+1]+i-pos-1-tmp);
}
}
}
printf("%d\n",dp[len]);
}
return 0;
}
分享到:
相关推荐
北大POJ3267-The Cow Lexicon
北大POJ3267-The Cow Lexicon 解题报告+AC代码
poj 1989 The Cow Lineup.md
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下
NULL 博文链接:https://128kj.iteye.com/blog/1754756
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
PKU Online Judge上面很全面的动态规划试题总结。动态规划是ACM考点中最重要的一大类算法之一,对于工作人员来说,动态规划也是实际开发中经常会遇到的算法。这是POJ上面很多DP题目的总结与深刻分析。利于算法学习,...
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
北大POJ1015-Jury Compromise【动态规划DP】 解题报告+AC代码
北大POJ初级-动态规划 解题报告+AC代码
北大POJ3176-Cow Bowling
动态规划算法poj1088滑雪实验报告 动态规划算法poj1088滑雪实验报告
动态规划DP题解 POJ HDU部分动态规划DP题解
动态规划 背包问题 动态规划 POJ 3267 POJ 1260 POJ 1015 POJ 3176 POJ 1080 POJ 1159 POJ 2533 POJ 1836 Leetcode 70 Leetcode 309 搜索 DFS POJ 2488 POJ 3083 POJ 3009 POJ 1321 BFS POJ 3278 POJ 1426 POJ 3126 ...
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ3278-Catch That Cow 解题报告+AC代码
动态规划DP题解 POJ HDU 动态规划解题报告
OJ动态规划DP题目列表 POJ SOJ HDU 动态规划题目
北大POJ1027-The Same Game 解题报告+AC代码