Mahmoud wrote a message s of length n. He wants to send it as a birthday PResent to his friend Moaz who likes strings. He wrote it on a magical paper but he was surprised because some characters disappeared while writing the string. That's because this magical paper doesn't allow character number i in the English alphabet to be written on it in a string of length more thana_i. For example, ifa₁?=?2 he can't write character 'a' on this paper in a string of length3 or more. String "aa" is allowed while string "aaa" is not.

Mahmoud decided to split the message into some non-empty substrings so that he can write every substring on an independent magical paper and fulfill the condition. The sum of their lengths should ben and they shouldn't overlap. For example, ifa₁?=?2 and he wants to send string "aaa", he can split it into "a" and "aa" and use 2 magical papers, or into "a", "a" and "a" and use3 magical papers. He can't split it into "aa" and "aa" because the sum of their lengths is greater thann. He can split the message into single string if it fulfills the conditions.

A substring of string s is a string that consists of some consecutive characters from strings, strings "ab", "abc" and "b" are substrings of string "abc", while strings "acb" and "ac" are not. Any string is a substring of itself.

While Mahmoud was thinking of how to split the message, Ehab told him that there are many ways to split it. After that Mahmoud asked you three questions:

Two ways are considered different, if the sets of split positions differ. For example, splitting "aa|a" and "a|aa" are considered different splittings of message "aaa".

The first line contains an integer n (1?≤?n?≤?10³) denoting the length of the message.

The second line contains the message s of length n that consists of lowercase English letters.

The third line contains 26 integersa₁,?a₂,?...,?a₂₆ (1?≤?a_x?≤?10³) — the maximum lengths of substring each letter can appear in.

Print three lines.

In the first line print the number of ways to split the message into substrings and fulfill the conditions mentioned in the problem modulo10⁹??+??7.

In the second line print the length of the longest substring over all the ways.

In the third line print the minimum number of substrings over all the ways.

3aab2 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1Output
322Input
10abcdeabcde5 5 5 5 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1Output
40143
題目解釋
給定一個字符串，對每個字母進行限制（只能出現在長度小于該字母限制的字符串中）。
在該限制下，將字符串分成若干個子串。
輸出該分配過程中，對字符串的分配種數，分配出的最長子串長度，分配出的最少子串數
題目分析
簡單dp
對字符串從長度為0時分析,dp[0]=0
當加入第i個字符時，對從s[i]往前長度為j（1~i）的字符串依次進行判定子串（s[i-j+1],s[i])是否能構成合法子串，
如果能，則有以下狀態轉移方程
dp[i]+=dp[i-j];//對字符串的分配種數
f[i]=min(f[i-j],f[i]);//分配出的最少子串數
MAX=max(MAX,j);//分配出的最長子串長度
AC代碼
#include<iostream>#include<string>#include<queue>#include<algorithm>using namespace std;int n, m;const int MAXN = 1e3 + 7;const int mod = 1e9 + 7;int limit[30];//每個字母使用限制long long dp[MAXN];//每個字符串的最多匹配方式int f[MAXN];//分配出的最少字串數char s[MAXN];//字符串int check(int i, int j)//檢查序列是否合法{	int l = j - i + 1;//i~j之間字符數，包含i，j	for (int k = i; k <= j; ++k)	{		if (limit[s[k] - 'a']<l)return 0;	}	return 1;}int main(){	int i, j;	while (cin >> n) {		cin >> s + 1;		for (i = 0; i < 26; ++i)			cin >> limit[i];		int MAX = 0;		dp[0] = 1;		for (i = 1; i <= n; ++i)//長度為i		{			f[i] = 1e9;			for (j = 1; j <= i; ++j)//長度			{				if (check(i - j + 1, i))//后面的當前序列合法				{					dp[i] = (dp[i] + dp[i - j]) % mod;//前i個字符分開的方法數					f[i] = min(f[i], f[i - j] + 1);//最小字串數					MAX = max(MAX, j);//最長字節				}			}		}		cout << dp[n] << endl;		cout << MAX << endl;		cout << f[n] << endl;	}	return 0;}
本文借鑒于http://blog.csdn.net/QQ_33362864/article/details/54925541
感謝原創