[CF766C] Mahmoud and a Message

Description

给出一串有小写字母组成的长度为 (n le 10^3) 的字符串。每个小写字母都有对应值 (a_i)，分割原串，要求对应值为 (a_i) 的字符不能出现在长度超过 (a_i) 的字串中。问共有多少种分割方式，分割后会出现的最长子串长度是多少，采用最少分割次数的方式，最少分割次数是多少？

Solution

dp，分别对三种询问进行处理，(O(n^2))

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
const int mod = 1e9+7;
const int inf = 1e9;

int f[N][3],a[N],n;
char s[N];

signed main() {
    ios::sync_with_stdio(false);
    cin>>n>>s+1;
    for(int i=0;i<26;i++) cin>>a[i];
    for(int i=1;i<=n;i++) f[i][2]=inf;
    f[0][0]=1;
    for(int i=1;i<=n;i++) {
        int l=a[s[i]-'a'];
        for(int j=i;j>=1;--j) {
            l=min(l,a[s[j]-'a']);
            if(i-j+1<=l) {
                f[i][0]=(f[i][0]+f[j-1][0])%mod;
                f[i][1]=max(f[i][1],max(f[j-1][1],i-j+1));
                f[i][2]=min(f[i][2],f[j-1][2]+1);
            }
        }
    }
    for(int i=0;i<3;i++) cout<<f[n][i]<<endl;
}