题目大意：给你长度为n的字符串（n<=1e6），让你对它进行划分，如果一段里面只有字母和

空格可以包含m（m<=1e5）个，如果有其他字符只能包含n个，问你最少需要分成几段。

 

思路：划分dp,dp[ i ] 表示以i为结束最少需要分成多少段，复杂度n*m，不能接受，我们考虑贪心

每次划分使其中包含的字符尽可能多，如果dp[ i ]没有赋值则直接跳过。

 

#include
      
       using namespace std;const int N=1e5+5;const int inf=0x3f3f3f3f;char s[N],g[3];int n,m,dp[N],ans;bool p[N];bool judge(char x){    if(x>='a' && x<='z') return true;    if(x>='A' && x<='Z') return true;    if(x==' ') return true;    return false;}int main(){    memset(dp,inf,sizeof(dp));    dp[0]=0;    ans=inf;    scanf("%d%d",&n,&m);    gets(g);    gets(s+1);    int len=strlen(s+1);    for(int i=0;i<=len;i++)    {        if(dp[i]==inf) continue;        bool flag=true;        int up=m;        for(int j=1;j+i<=len && j<=m;j++)        {            if(!judge(s[i+j])) flag=false,up=n;            if(j<=n && !flag)            {                int to=min(len,i+n);                dp[to]=min(dp[to],dp[i]+1);                break;            }            else if(j>n && !flag)            {                int to=min(len,i+j-1);                dp[to]=min(dp[to],dp[i]+1);                break;            }        }        if(up==m) dp[min(i+m,len)]=min(dp[min(i+m,len)],dp[i]+1);    }    //cout<
       
        <