codeforces 766 C. Mahmoud and a Message（简单dp）

题目链接：http://codeforces.com/contest/766/problem/C

题意：给你一个长度为n的字符串，这个字符串只包含小写字母，然后让你把这个字符串进行分割，形成若干个小的字符串，

每个小写字母都有一个数字ma[i]，表示这个字母能够存在于长度不超过ma[i]的字符串内， 在这个条件下分割问最多有几

种分割方法，最长分割串为多少，最小分割为几部分。

一道简单的dp，很明显要设dp[i]表示到i位一共有几种分割方法然后递推，注意更新过程中要满足所有子串。然后再设f[i]

表示到前i位最小分割为几部分，然后差不多。

大致转移如下。

for(int i = 1 ; i <= n ; i++) {

for(int j = 1 ; j <= i ; j++) {//递推

int l = i – j + 1 , r = i;

int flag = 0;

for(int k = l ; k <= r ; k++) {//使得范围内所有子串满足条件后再修改

int len = r – l + 1;

if(el[s[k] – ‘a’] < len) {

flag = 1;

break;

}

}

if(!flag) {

dp[i] = (dp[i] + dp[i – j]) % mod;

MINF[i] = min(MINF[i] , MINF[i – j] + 1);

MAX = max(MAX , j);

}

}

}

#include <iostream>
#include <cstring>
#define inf 0X3f3f3f3f
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
char s[1010];
int el[26] , MAX , MINF[1010];
ll dp[1010];
int main() {
    int n;
    cin >> n;
    cin >> s + 1;
    for(int i = 0 ; i < 26 ; i++) {
        cin >> el[i];
    }
    memset(dp , 0 , sizeof(dp));
    memset(MINF , inf , sizeof(MINF));
    dp[0] = 1 , MAX = 1 , MINF[0] = 0;
    for(int i = 1 ; i <= n ; i++) {
        for(int j = 1 ; j <= i ; j++) {
            int l = i - j + 1 , r = i;
            int flag = 0;
            for(int k = l ; k <= r ; k++) {
                int len = r - l + 1;
                if(el[s[k] - 'a'] < len) {
                    flag = 1;
                    break;
                }
            }
            if(!flag) {
                dp[i] = (dp[i] + dp[i - j]) % mod;
                MINF[i] = min(MINF[i] , MINF[i - j] + 1);
                MAX = max(MAX , j);
            }
        }
    }
    cout << dp[n] << endl;
    cout << MAX << endl;
    cout << MINF[n] << endl;
    return 0;
}