【wikioi】1040 统计单词个数

缺乏、安全感 2022-03-31 04:24 279阅读 0赞

[题目链接][Link 1]

算法：划分型DP

PS：被卡过3天。日期：2013-10-10 ~ 2013-10-12 18:52:48

这题是我提交了13次AC= =汗= =

题目描述：

> 给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。要求将此字母串分成k份(1<k<=40)，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可包含this和is，选用this之后就不能包含th)（管理员注：这里的不能再用指的是位置，不是字母本身。比如thisis可以算做包含2个is）。  
> 单词在给出的一个不超过6个单词的字典中。  
> 要求输出最大的个数。

注意：

1、此题和[【wikioi】1017 乘积最大][wikioi_1017]  的性质差不多，都是划分k份（1017是添乘号，其实就是分k+1份）

2、唯一不同的是，判断单词是一个整体，少一个就不能加入，所以要特别注意

3、此题预处理恶心，就是在主DP前还要DP一个二维数组a，a\[i\]\[j\]表示下标i->j单词数（恶心就恶心在更新这里，我是看了别人的题解的= =）

首先是主方程DP：

我们用F\[n\]\[k\]来表示0到n（因为是字符串，我用string存的）划分成k份得到的数最大

得到：

**F\[i\]\[1\] = a\[1\]\[i\]  (0 <= i < str.size())**

**F\[i\]\[k\] = max(F\[i\]\[k\], A\[j+1\]\[i\]\*F\[j\]\[k-1\]) (k-1 <= j < i, 2 <= k <= m) //m是要分成的份数**

**//想想为什么是k-1而不是k？ 因为是分成k份，相当于有k-1个乘号**

for(int l = 2; l <= k; l++)
    	for(int i = l-1; i < str.size(); i++)
    		for(int j = i-1; j >= l-1; j--)
    			f[i][l] = max(f[i][l], f[j][l-1] + a[j+1][i]);

然后到初始化a数组的DP：

我们从字符串屁股找起（j=str.size()-1  -> 0），每一次设i从j到0更新a\[i\]\[j\]

很容易得到方程

**a\[i\]\[j\] = a\[i+1\]\[j\] + 1 (以i为下标找到一个单词（必须以i为单词的第一个下标）)**

**a\[i\]\[j\] = a\[i+1\]\[j\]       (以i为下标找不到单词，就等于i+1->j的单词数)**

//dic是存单词的，str是整个字符串
    int yes, i, j, l;
    for(j = str.size()-1; j >= 0; j--)
    	for(i = j; i >= 0; i--)
    	{
    		for(l = 0; l < s; l++)
    		{
    			yes = 0;
    			//其实就是看str[j]到i后面是否加了新单词，加了就直接退出（即使有相同的串，更何况不相同的了）
    			if(str.find(dic[l], i) == i && dic[l].size() <= j-i+1) yes = 1; //如果以i开头找到新单词
    			/* //也可以这样
    			if(str[i] == dic[l][0] && dic[l].size() <= j-i+1)
    			{
    				yes = 1;
    				for(int p = 0; p < dic[l].size(); p++)
    					if(str[i+p] != dic[l][p])
    					{
    						yes = 0; break;
    					}
    			}
    			*/
    			if(yes) break;
    		}
    		if(yes) a[i][j] = a[i+1][j]+1;
    		else    a[i][j] = a[i+1][j];
    	}

总结：

1、贪心策略用错：

错：判断是否有前缀，有前缀就跳过。（贪心，因为有了前缀的话，应该用短的，将长的去掉）

正解：不需要此贪心，在dp中已包含

2、一直认为是某个点错，没考虑是整体错误

3、被数据坑得以为对，一直提交

以后多多注意= =

放上全部代码：

#include <iostream>
    #include <string>
    #include <cstring>
    using namespace std;
    
    string str, dic[6];
    bool cdic[6][6], used[6];
    int a[210][210], f[210][40], k, s;
    
    void chu() //初始化a数组，a[i][j]表示下标i->j单词数
    {
    	memset(a, 0, sizeof(a));
    	int yes, i, j, l;
    	for(j = str.size()-1; j >= 0; j--)
    		for(i = j; i >= 0; i--)
    		{
    			for(l = 0; l < s; l++)
    			{
    				yes = 0;
    				//其实就是看str[j]到i后面是否加了新单词，加了就直接退出（即使有相同的串，更何况不相同的了）
    				if(str.find(dic[l], i) == i && dic[l].size() <= j-i+1) yes = 1; //如果以i开头找到新单词
    				/* //也可以这样
    				if(str[i] == dic[l][0] && dic[l].size() <= j-i+1)
    				{
    					yes = 1;
    					for(int p = 0; p < dic[l].size(); p++)
    						if(str[i+p] != dic[l][p])
    						{
    							yes = 0; break;
    						}
    				}
    				*/
    				if(yes) break;
    			}
    			if(yes) a[i][j] = a[i+1][j]+1;
    			else    a[i][j] = a[i+1][j];
    		}
    }
    
    void dp()
    {
    	memset(f, 0, sizeof(f));
    	for(int i = 0; i < str.size(); i++)
    		f[i][1] = a[0][i];
    	for(int l = 2; l <= k; l++)
    		for(int i = l-1; i < str.size(); i++)
    			for(int j = i-1; j >= l-1; j--)
    				f[i][l] = max(f[i][l], f[j][l-1] + a[j+1][i]);
    }
    
    void print()
    {
    	cout << f[str.size()-1][k] << endl;
    }
    
    void init()
    {
    	string temp;
    	int n, p;
    	cin >> n;
    	while(n--)
    	{
    		cin >> p >> k;
    		str = "";
    		while(p--)
    		{
    			cin >> temp; str += temp;
    		}
    		cin >> s;
    		for(int i = 0; i < s; i++)
    			cin >> dic[i];
    		chu();
    		dp();
    		print();
    
    	}
    }
    
    int main()
    {
    	init();
    	return 0;
    }

[Link 1]: http://www.wikioi.com/problem/1040/
[wikioi_1017]: http://iwtwiioi.f3322.org:7654/oi/%E3%80%90wikioi%E3%80%911017-%E4%B9%98%E7%A7%AF%E6%9C%80%E5%A4%A7/