題意：

給一串字符串，只包含26個字母，可以把這串字符串分成若干個子串，但是限定每個字母只能出現(xiàn)在長度Ax的子串里，問最多有多少種分割方案，方案數(shù)對1e9+7取膜，以及分割子串最大長度，和最少分割子串?dāng)?shù)量。

解題思路：

設(shè)dp[i]為從0到i這段字符串的分割方案數(shù)，為了滿足字符a[i]的限定條件，我們只能在i-Ai+1到i之間劃分，設(shè)len=i-A[i]+1， 但是i-A[i]+1并不就是可以劃分的長度，因?yàn)樵趇-Ai+1到i有些字母的限定子串長度會小于i-A[i]+1，所以我們可以設(shè)一個指針j從i這個點(diǎn)開始往下枚舉，讓len不斷更新，當(dāng)i-j+1>len的時候跳出，所以指針j在跳出之前，都是可以劃分的點(diǎn)，假如我們在j這個點(diǎn)劃分的話，這就是一種劃分的方案，同時我們需要加上j這個點(diǎn)之前的劃分方案數(shù)，也就是dp[j-1]，所以每次枚舉都要更新:dp[i]=(dp[i]+dp[j-1])%mod。這樣就能求出最大方案數(shù)了。

而最大子串長度也就是最大的len，最少劃分?jǐn)?shù)可以再開一個dp[i]記錄到i這個點(diǎn)的最小劃分?jǐn)?shù)，在枚舉合法劃分點(diǎn)j的時候找到最小的dp[j]，然后dp[i]=dp[j]+1就行。

代碼：

#include <bits/stdc++.h>using namespace std;const int maxn=1e3+5;const int mod=1e9+7;char a[maxn];int dp[maxn];int spil[maxn];int s[28];int main(){    int n;    scanf("%d", &n);    scanf("%s", a+1);    int i, j;    for(i=0; i<26; i++)scanf("%d", &s[i]);    dp[0]=1;    int len;    int lmax=0, mi=0;    spil[0]=0;    for(i=1; a[i]; i++)    {        len=s[a[i]-'a'];        spil[i]=mi=10000;        for(j=i; j>=1; j--)        {            len=min(len, s[a[j]-'a']);            if(i-j+1>len)break;            dp[i]=(dp[i]+dp[j-1])%mod;            lmax=max(lmax, i-j+1);            mi=min(mi, spil[j-1]);        }        spil[i]=mi+1;    }    PRintf("%d/n%d/n%d/n", dp[n], lmax, spil[n]);    return 0;}