题意:
有一个字符串以及有很多单词的字典,求在字符串中删除最少的单词数,使字符串和字典中的单词完全匹配。
要点:
这题我是没想出来,看了网上大神的解题报告。重点就是用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;
}