洛谷P1026 统计单词个数

柔情只为你懂 2022-05-27 13:45 188阅读 0赞

## 题目描述 ##

给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。要求将此字母串分成k份(1<k<=40)，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可包含this和is，选用this之后就不能包含th)。

单词在给出的一个不超过6个单词的字典中。

要求输出最大的个数。

## 输入输出格式 ##

输入格式：

每组的第一行有二个正整数(p，k)

p表示字串的行数;

k表示分为k个部分。

接下来的p行，每行均有20个字符。

再接下来有一个正整数s，表示字典中单词个数。(1<=s<=6)

接下来的s行，每行均有一个单词。

输出格式：

一个整数，分别对应每组测试数据的相应结果。

## 输入输出样例 ##

输入样例\#1： 复制

1 3
    thisisabookyouareaoh
    4
    is
    a
    ok
    sab

输出样例\#1： 复制

## 说明 ##

this/isabookyoua/reaoh

参考：[https://www.luogu.org/blog/user42653/solution-p1026][https_www.luogu.org_blog_user42653_solution-p1026]

初看这题，毫无头绪，真的时毫无头绪，不知道如何下手，看了题解，还是有些不太明白，唉，我的水平，咋就。。。

#include<iostream>
    #include<algorithm>
    #include<stdio.h>
    using namespace std;
    
    char text[210];
    char words[6][210];
    int p, k, s;
    int dp[41];
    int t[210];
    
    void coutdp1()
    {
    	for (int i = 1; i <= p * 20;i++)
    	for (int j = 0; j < s; j++)
    	{
    		int k;
    		for ( k = 0; words[j][k]; k++)
    		{
    			if (words[j][k] != text[i+k])
    				break;
    		}
    		if (!words[j][k])
    		{
    			dp[1]++;
    			break;
    		}
    	}
    }
    
    int main()
    {
    	//freopen("1.txt", "r", stdin);
    	cin >> p >> k;
    	for (int i = 0; i < p; i++)
    		cin >> text + i * 20 + 1;
    
    	cin >> s;
    	for (int i = 0; i < s; i++)
    		cin >> words[i];
    
    	coutdp1();
    	
    	for (int i = 2; i <= k; i++)//分成k段
    	{
    		int minnum = 9999; int g;
    		for (int j = 1; j <= p * 20-1; j++)//遍历要分的点
    		{
    			if (!t[j])//如果该点没被分过就进入判断
    			{
    				int tmp = 0;
    				for (int m = 0; m < s;m++)
    				for (int n = 0; words[m][n+1]; n++)//得保证字符串的长度>1吧，要不然j和j+1切不来哦切不了
    				{
    					if (words[m][n] == text[j] && words[m][n + 1] == text[j + 1])//分割单词，在j和j+1间切一刀试试
    					{
    						tmp++;
    						break;
    					}
    				}
    				if (minnum>tmp)
    				{
    					minnum = tmp;
    					g= j;//找到每次分开使得失去单词数最小的切开点
    				}
    			}
    		}
    		dp[i] = dp[i - 1] - minnum;
    		t[g] = 1;
    
    	}
    	cout << dp[k];
    	return 0;
    }

[https_www.luogu.org_blog_user42653_solution-p1026]: https://www.luogu.org/blog/user42653/solution-p1026