题解 P1026 【统计单词个数】
千反田
·
·
题解
这里讲一下我和其他题解有点不一样的思路QAQ
首先珂以知道这是一道DP
这道题的思路和P1018乘积最大的思路有点像
把一个单词分成 k 份就相当于在单词中放置 (k-1) 条分割线
为方便说明，下文把 (k-1) 直接用 k 表示
设 f[i][j] 为在第 i 个字母后放第 j 个分割线，前 i 个单词所能获得的最大价值
注意每份单词不能为空
最后统计答案的时候在 f[i][k](k<=i<=n-k)+(i+1,n)对答案的贡献，扫一遍取个 max
case1：如何转移？
我的想法还是比较暴力的，首先初始化 f[i][1] 全部为初始化为(1,i)这个区间对答案的贡献
第一层循环j枚举正在放置第j个分割线(2<=j<=k)；
第二层循环i枚举分割线放置的位置(j<=i<=n-1);
最后一层循环l枚举从前面的哪个状态转移过来
也就是在(f[l][j-1]+(l+i,i)这个区间对答案的贡献)中取 max (j-1<=l<=i-1)
rep(i,1,n-1)
f[i][1]=query(1,i);
rep(j,2,k)
rep(i,j,n-1)
rep(l,j-1,i-1)
f[i][j]=max(f[i][j],f[l][j-1]+query(l+1,i));
### case2:如何统计一个区间对答案的贡献
显然一个区间对答案的贡献就是一个区间中字典中单词个数(去重后)
题目中给出了一个限制:**当选用一个单词之后，其第一个字母不能再用。**
那我们就珂以依次对字典中的每个字符串进行匹配，如果匹配成功就将该字符匹配位置的开头标记为匹配过，下回如果匹配到同一位置既不合法，跳过该次匹配
```cpp
//本人习惯字符串下标从1开始
inline int cnt(int index,int l,int r){
int len=r-l-strlen(word[index]+1)+2,res=0;//len为匹配次数，res为该字符串的贡献
rep(i,0,len-1)
rep(j,1,strlen(word[index]+1))
if((word[index][j]^str[l+i+j-1])||(trace[l+i]))
break;
else
if(j==strlen(word[index]+1))
++res,trace[l+i]=true;
return res;
}
inline int query(int l,int r){
rep(i,l,r)
trace[i]=false;
int res=0;
rep(i,1,s)//依次对每个字符串进行匹配
if(r-l+1>=strlen(word[i]+1))//如果区间长度>字符串长度
res+=cnt(i,l,r);//统计该字符串的贡献
return res;
}
```
## 祭上代码：
```cpp
#include<bits/stdc++.h>
#define rint register int
#define rc register char
#define rll register long long
#define rep(i,j,k) for(rint i=j;i<=k;++i)
#define dow(i,j,k) for(rint i=j;i>=k;--i)
#define MAXN 205
#define N 10
int p,k,ans=0,s,n;
char str[MAXN];
int f[MAXN][MAXN];
char word[N][MAXN];
bool trace[MAXN];
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}//手写较快
inline int cnt(int index,int l,int r){
int len=r-l-strlen(word[index]+1)+2,res=0;//len为匹配次数，res为该字符串的贡献
rep(i,0,len-1)
rep(j,1,strlen(word[index]+1))
if((word[index][j]^str[l+i+j-1])||(trace[l+i]))
break;
else
if(j==strlen(word[index]+1))
++res,trace[l+i]=true;
return res;
}
inline int query(int l,int r){
rep(i,l,r)
trace[i]=false;
int res=0;
rep(i,1,s)//依次对每个字符串进行匹配
if(r-l+1>=strlen(word[i]+1))//如果区间长度>字符串长度
res+=cnt(i,l,r);//统计该字符串的贡献
return res;
}
void calc(){/程序核心dp
rep(i,1,n-1)
f[i][1]=query(1,i);
rep(j,2,k)
rep(i,j,n-1)
rep(l,j-1,i-1)
f[i][j]=max(f[i][j],f[l][j-1]+query(l+1,i));
rep(i,k,n-k)
ans=max(ans,f[i][k]+query(i+1,n));
}
void Debug(){//个人调试用
rep(i,1,s)
printf("%s\n",word[i]+1);
rep(i,1,n)
rep(j,1,k)
printf("f[%d][%d]=%d\n",i,j,f[i][j]);
}
int main(){
scanf("%d %d\n",&p,&k);
--k;//分割线数量
rep(i,1,p)
scanf("%s",str+20*(i-1)+1);//s每次输入把字符串拼接到下标为20*(i-1)+1上，+1是因为下标从1开始
n=strlen(str+1);
scanf("%d",&s);
rep(i,1,s)
scanf("%s",word[i]+1);//下标从1开始
calc();
//Debug();
printf("%d\n",ans);
}
```
~~第一次提交忘了把Debug注释掉居然还有20？你谷评测机太玄学~~