又是一道让sy coding 1h,调试2h的好题呢
--------------------(手动分割)-----------------------------------------
传送
看题第一眼：区间(dp)!
看题第二眼：好像不是区间(dp)
看题第三眼：
@语文老师 老师这段话在说啥？？？
语文老师不理我并把我丢出去
这段话就是说，把选的所有单词左对齐，不能有任意一个短单词和某个长单词的前(len_{短单词})位一样。将例子中的(this,th,is)左对齐之后，发现(this)的前2位（也就是(th)的长度）和(th)是一样的，所以不能选(th)。
感性李姐
好了我们来看怎么(dp)
既然分的段数固定，那么我们不妨将当前分了几段加入状态中。可以自然而然想到(dp[i][j])表示前(i)位分成(j)份的最大单词数。显然，(dp[i][j]=max{ dp[l][j-1]+cnt[l+1][i] },l in [j,i-1])。其中(cnt[i][j])表示文本串（下标从1开始），([i,j])中有多少个单词。
那么(cnt)怎么算呢？由于题目限制于首字母有关，那么我们可以倒着推，(cnt[i][j]=cnt[i+1][j]+find(i,j-i+1)),其中(find(i,j))表示从文本串的第(i)位开始，长度为(j)的串中是否包含至少一个模式串，可以用暴力实现。
处理(cnt):
int fd(int x,int l)
{
for(int i=1;i<=s;i++)
{
int len=strlen(mo[i]+1);
bool ok=0;
if(len>l) continue;
for(int j=1;j<=len;j++)
if(mo[i][j]!=wa[x+j-1])
{ok=1;break;}
if(!ok) return 1;//找到之后立刻返回
}
return 0;
}
for(int j=tot;j>=1;j--)
for(int i=j;i>=1;i--)
cnt[i][j]=cnt[i+1][j]+fd(i,j-i+1);//这里简写为fd
最后就是(dp)了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
char ch=getchar();
ll x=0;bool f=0;
while(ch<'0'||ch>'9')
{
if(ch=='-') f=1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return f?-x:x;
}
int p,k,s,dp[209][59],cnt[409][409];
char wb[50][29],mo[8][22],wa[509];
int fd(int x,int l)
{
for(int i=1;i<=s;i++)
{
int len=strlen(mo[i]+1);
bool ok=0;
if(len>l) continue;
for(int j=1;j<=len;j++)
if(mo[i][j]!=wa[x+j-1])
{ok=1;break;}
if(!ok) return 1;
}
return 0;
}
int main()
{
p=read();k=read();
for(int i=1;i<=p;i++)
scanf("%s",wb[i]+1);
int tot=0;
for(int i=1;i<=p;i++)
{
int len=strlen(wb[i]+1);
for(int j=1;j<=len;j++)
wa[++tot]=wb[i][j];
}
s=read();
for(int i=1;i<=s;i++)
scanf("%s",mo[i]+1);
for(int j=tot;j>=1;j--)
for(int i=j;i>=1;i--)
cnt[i][j]=cnt[i+1][j]+fd(i,j-i+1);
for(int i=1;i<=k;i++) dp[i][i]=dp[i-1][i-1]+cnt[i][i];
for(int i=1;i<=tot;i++) dp[i][1]=cnt[1][i];
for(int i=1;i<=tot;i++)
{
for(int j=1;j<=k&&j<i;j++)
{
for(int l=j;l<=i-1;l++)
{
dp[i][j]=max(dp[i][j],dp[l][j-1]+cnt[l+1][i]);
}
}
}
printf("%d",dp[tot][k]);
}
尾声之博主的疑惑
如果把(l)的左边界改为(j-1),同时不处理边界，也是可以(AC)的，并且拍了几百组数据并没有(WA)过。所以有人知道这是为什么吗？
充满迷惑的伪？AC代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
char ch=getchar();
ll x=0;bool f=0;
while(ch<'0'||ch>'9')
{
if(ch=='-') f=1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return f?-x:x;
}
int p,k,s,dp[209][59],cnt[409][409];
char wb[50][29],mo[8][22],wa[509];
int fd(int x,int l)
{
for(int i=1;i<=s;i++)
{
int len=strlen(mo[i]+1);
bool ok=0;
if(len>l) continue;
for(int j=1;j<=len;j++)
if(mo[i][j]!=wa[x+j-1])
{ok=1;break;}
if(!ok) return 1;
// if(mo[i][1]==wa[x]) return 1;
}
return 0;
}
int main()
{
// freopen("wa.in","r",stdin);
// freopen("ans.txt","w",stdout);
p=read();k=read();
for(int i=1;i<=p;i++)
scanf("%s",wb[i]+1);
int tot=0;
for(int i=1;i<=p;i++)
{
int len=strlen(wb[i]+1);
for(int j=1;j<=len;j++)
wa[++tot]=wb[i][j];
}
s=read();
for(int i=1;i<=s;i++)
scanf("%s",mo[i]+1);
for(int j=tot;j>=1;j--)
for(int i=j;i>=1;i--)
cnt[i][j]=cnt[i+1][j]+fd(i,j-i+1);//,printf("cnt[%d][%d]=%d
",i,j,cnt[i][j]);
// for(int i=1;i<=k;i++) dp[i][i]=dp[i-1][i-1]+cnt[i][i];
// for(int i=1;i<=tot;i++) dp[i][1]=cnt[1][i];
for(int i=1;i<=tot;i++)
{
for(int j=1;j<=k&&j<=i;j++)
{
for(int l=j-1;l<=i-1;l++)
{
dp[i][j]=max(dp[i][j],dp[l][j-1]+cnt[l+1][i]);
}
}
}
printf("%d",dp[tot][k]);
}