题目链接：https://www.luogu.com.cn/problem/P1026
感觉可以贪心，但是贪心只过了两个点╮(╯▽╰)╭
我的思路是这样的：我们从后往前去记录出现单词，数据量小完全可以暴力，然后将单词标记一下，首字母额外标记一下。
最后我们统计出有多少个单词，下面开始分割，如果没有被共用的字母大于k那么就输出ans，否则就从中减去。
——————————————————————————————————————————————————————————
在题解中终于翻到了一个和我思路很像的贪心做法。意料之中的是贪心的做法代码量确实少。这个题要dp就需要预处理一些东西
我贪心没有做好的一点就是被共用的字母我并没有去找一个最优解，这一部完全可以使用dp[i]来解决，从2-k直接贪心一下。每次找最少的切入点
——————————————————————————————————————————————————————————
再来看看dp做法，也是大部人的做法。 没有想到==
首先我们完全可以去处理每个分段的单词数量，这一步不难，然后预处理一下dp数组
在dp数组中，我们列举 结尾 段数 和至少开始的部分。
当前前i个字母中，分成j段。跟末尾字母后一项有关。l开头说明我们要用这个字母了，所以转移状态一定是上个分段+ （l+1,i）这一步已经预处理了；
dpcode：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define cyes cout<<"YES\n"
#define cno cout<<"NO\n"
#define mem(a) memset((a),0,sizeof (a))
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int nn = 210;
string s;
string a[10];
int sum[nn][nn];
int dp[nn][50];
int n;
int p,k;
bool check(int l,int r){
string x = s.substr(l,r-l+1);
for(int i=1;i<=n;i++)
if(x.find(a[i])==0) return true;
return false;
}
int main()
{
s+='0';
cin>>p>>k;
string c;
for(int i=1;i<=p;i++){
cin>>c;
s+=c;
}
int m = s.size()-1;
cin>>n;
for(int i =1;i<=n;i++)
cin>>a[i];
for(int i=m;i>=1;i--)//没什么好说的从位置从i - j的单词数
for(int j=i;j>=1;j--){
sum[j][i] = sum[j+1][i];
if(check(j,i)) sum[j][i]++;
}
dp[0][0] = 0;
for(int i=1;i<=k;i++) dp[i][i] = dp[i-1][i-1] + sum[i][i];
for(int i=1;i<=m;i++) dp[i][1] = sum[1][i];
for(int i=1;i<=m;i++)//以i结尾
for(int j=1;j<=k&&j<i;j++)//分成j段的
for(int l=j;l<i;l++)//第j段至少从第j个位置开始
dp[i][j] = max(dp[i][j],dp[l][j-1]+sum[l+1][i]);//l用了就不能再用了
cout<<dp[m][k]<<endl;
}
贪心code：
#include<stdio.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define LEN 20
char c[201] = {0}, word[6][200] = {0};
int d[41] = {0}, t[41] = {0};
int main()
{
int p, k, s, i, j, m, n, f, g, minum;
scanf("%d%d", &p, &k);
for(i = 0; i < p; i++)
scanf("%s", c+i*LEN+1);
scanf("%d", &s);
for(i = 0; i < s; i++)
scanf("%s", word[i]);
for(i = 1; i <= p*LEN; i++)
for(j = 0; j < s; j++)
{
for(m = 0; word[j][m] != 0; m++)
if(word[j][m] != c[i+m])
break;
if(word[j][m] == 0)
{
d[1]++;
break;
}
}
for(i = 2; i <= k; i++)
{
minum = 99999;
for(j = 1; j <= p*LEN-1; j++)
if(!t[j])
{
f = 0;
for(m = 0; m < s; m++)
for(n = 0; word[m][n+1] != 0; n++)
if(word[m][n] == c[j] && word[m][n+1] == c[j+1])
{
f++;
break;
}
if(minum > f)
{
minum = f;
g = j;
}
}
d[i] = d[i-1]-minum;
t[g] = 1;
}
printf("%d\n", d[k]);
return 0;
}