洛谷P1026 统计单词个数

https://www.luogu.org/problemnew/show/P1026

对这句话“当选用一个单词之后，其第一个字母不能再用”需要特殊处理一下，贪心，如果包含this，th，t则等价于只包含t，即几个单词开头相等并且有完全包含关系，则保留最短的那个即可，针对上述3个单词给个例子：thisththis.

设g(i,j):字符串从i到j位置的单词总数。

g(i,j)=g(i+1,j)+g(i,j-1)-g(i+1,j-1)，因为区间扩大时必须考虑端点新加入的字母和原先中间字符串合并的单词数，

边界就是：在字符串中，那几个单词所在区间的单词总数为1。

（ps：刚开始想着g(i,j)=max{g(i,k)+g(k+1,j)}是错的，反例：the，单词：th和he）

设f(i,j):把字符串从第i个字符到结尾分成j份的最大单词数，

则f(i,j)=max{f(l,j-1)+g(i,l-1)}

注意边界之外 最近写DP总是出很多bug

#include<bits/stdc++.h>
using namespace std;

int p,k,len,n;
char s[205];
char word[7][205];
int len_word[7];

int f[205][45];
int g[205][205];

void solve_divide()
{
	for(int i=len;i>=1;i--)
	{
		f[i][1]=g[i][len];
		for(int j=2;j<=k;j++)
		{
			for(int l=i+1;l<=len&&len-l+1>=j-1;l++)
			{  //注意&&后面的，n个元素不能被分为n+1份，这里是边界之外 
			//如果不特判，例子：aaa分3份，单词是aa，计算aa分一份，最后一个a分两份，方案数应该是0被计算出1+0=1种
			//边界之外赋初值-INF也可。 
				f[i][j]=max(f[l][j-1]+g[i][l-1],f[i][j]);
			//即开始时写上这句fill(f[0],f[0]+205*45,-(1<<30));
			//和&&右面选一个写即可 
			}				
		}
	}
}

void solve_word()
{
	for(int i=1;i<=n;i++)len_word[i]=strlen(word[i]);
	for(int i=1;i<=n;i++)
	 	for(int j=1;j<=n;j++)
	 	{
	 		if(i==j)continue;
	 		if(len_word[i]>=len_word[j]&&len_word[j]!=0)
	 		{               //空字符串是任何字符串的子字符串 
	 			if(strncmp(word[i],word[j],len_word[j])==0)
	 			{
	 				word[i][0]=\'\\0\';
	 				len_word[i]=0;
				 }
			 }
		 }
	for(int i=1;i<=len;i++)
	{
		for(int j=1;j<=n;j++)if(len_word[j]!=0&&strncmp(s+i,word[j],len_word[j])==0)
			g[i][i+len_word[j]-1]=1;
	}
	for(int k=2;k<=len;k++)
		for(int i=1;i<=len;i++)
		{
			int j=i+k-1;				
			if(j<=len)g[i][j]+=g[i][j-1]+g[i+1][j]-g[i+1][j-1];
		}
}

void init()
{
	cin>>p>>k;
	len=1;
	for(int i=1;i<=p;i++)
	{
		cin>>s+len;
		len+=20;
	}
	len--;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>word[i];
}

void debug()
{
//	for(int i=1;i<=len;i++)
	{
//		for(int j=i;j<=len;j++)printf(\"[%d,%d]:%d\\n\",i,j,g[i][j]);
  	}
  	for(int i=1;i<=len;i++)for(int j=1;j<=k;j++)printf(\"f(%d,%d):%d\\n\",i,j,f[i][j]);
}

int main()
{
	freopen(\"input.in\",\"r\",stdin);
	init();
	solve_word();
	solve_divide();
//	debug();
	cout<<f[1][k]<<endl;
	return 0;
}