我用的比较传统的办法。。。单调队列优化了一下，写的有点搓，不管怎样过了。。。两个单调队列，存两个东西，预处理一个标记数组存。。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <algorithm>
using namespace std;
#define INF 1000000
char str[];
int dp[];
int pre[];
int que1[];
int que2[];
int judge(char s)
{
if(s <= 'Z'&&s >= 'A')
return ;
else if(s <= 'z'&&s >= 'a')
return ;
else if(s == ' ')
return ;
else
return ;
}
int main()
{
int n,m,i,j,len,str1,end1,str2,end2;
scanf("%d%d%*c",&n,&m);
gets(str);
len = strlen(str);
for(i = ; i < len; i ++)
{
if(judge(str[i]))
{
for(j = i; j < len; j ++)
{
if(judge(str[j]))
pre[j] = i;
else
{
i = j;
break;
}
}
if(j == len) break;
}
}
for(i = ;i <= len;i ++)
dp[i] = INF;
str1 = ;end1 = ;
str2 = ;end2 = ;
que1[] = que2[] = ;
for(i = ;i <= len;i ++)
{
dp[i] = dp[que1[str1]] + ;
if(judge(str[i-]))
{
if(str2 < end2)
dp[i] = min(dp[i],dp[que2[str2]]+);
}
else
{
str2 = end2 = ;
}
if(i == len) continue;
while(str1 < end1&&dp[i] <= dp[que1[end1-]])
end1 --;
que1[end1++] = i;
while(str1 < end1&&i - que1[str1] >= n)
str1 ++;
if(judge(str[i]))
{
while(str2 < end2&&dp[i] <= dp[que2[end2-]])
end2 --;
que2[end2++] = i;
while(str2 < end2&&que2[str2] < pre[i])
str2 ++;
while(i - que2[str2] >= m&&str2 < end2)
str2 ++;
}
}
printf("%d\n",dp[len]);
return ;
}