题目链接:https://codeforces.com/contest/766/problem/C
题目大意:给出一串有小写字母组成的长度为n的字符串。每个小写字母都有对应值ai,分割原串,要求对应值为ai的字符不能出现在长度超过ai的字串中。问共有多少种分割方式,分割后会出现的最长子串长度是多少,采用最少分割次数的方式,最少分割次数是多少?

思路:f[i]:以第i个字符结尾的分割方案数。p[i]:以第i个字符结尾的分割方案数最多字符串个数。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int mod=1e9+7;
 
int s[35]={0};
char a[1005];
LL f[1005]={0};
LL p[1005]={0};
int c[1005][27]={0};
int main()
{
    int n, M1=1;
    scanf("%d", &n);
    scanf("%s", a+1);
    for(int i=1; i<=26; i++){
        scanf("%d", &s[i]);
    }
    f[0]=1,f[1]=1, p[1]=1, c[1][a[1]-'a'+1]++;
    for(int i=2; i<=n; i++){
            p[i]=1<<30;
        for(int j=1; j<=26; j++){
            c[i][j]+=c[i-1][j];
        }
        c[i][a[i]-'a'+1]++;
        for(int j=1; j<=i; j++){
            int g=0, Len=i-j+1;
            for(int k=1; k<=26; k++){
                if(c[i][k]-c[j-1][k]){
                    if(s[k]<Len){
                        g=1;
                    }
                }
            }
            if(!g){
                f[i]=(f[i]+f[j-1])%mod;
                M1=max(M1, Len);
                p[i]=min(p[i], p[j-1]+1);
 
                //cout<<i<<" "<<j<<" "<<f[i]<<endl;
            }
        }
    }
    printf("%lld\n%d\n%d\n", f[n], M1, p[n]);
 
    return 0;
}