当前位置: 代码迷 >> 综合 >> POJ3267 The Cow Lexicon(DP)
  详细解决方案

POJ3267 The Cow Lexicon(DP)

热度:75   发布时间:2024-01-16 13:37:16.0

题意:

有一个字符串以及有很多单词的字典,求在字符串中删除最少的单词数,使字符串和字典中的单词完全匹配。

要点:

这题我是没想出来,看了网上大神的解题报告。重点就是用dp[i]表示从i 到字符串末尾n要删除的最小数目,后面再分为能匹配和不能匹配进行状态转移。

参考博客:点击打开链接


15695630 Seasonal 3267 Accepted 196K 79MS C++ 830B 2016-07-10 14:02:58
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
char words[605][30],message[350];
int dp[350];int main()
{int i, j,m,n;while (scanf("%d%d", &m, &n) != EOF){scanf("%s", message);for (i = 0; i < m; i++)scanf("%s", words[i]);dp[n] = 0;for (i = n - 1; i >= 0; i--){dp[i] = dp[i + 1] + 1;//如果不能匹配for (j = 0; j < m; j++){int len = strlen(words[j]);if (len <= n - i&&words[j][0] == message[i])//匹配剩下的字符数要多于单词字符数{int pm = i;//message的指针int pd = 0;//单词的指针while (pm < n){if (words[j][pd] == message[pm++])pd++;if (pd == len){dp[i] = min(dp[i], dp[pm] + (pm - i) - len);//pm比len多移动的数目就是要删除的个数break;}}}}}printf("%d\n", dp[0]);}return 0;
}