Code Forces 766C - Mahmoud and a Message（思维）

 1 #include <iostream>
 2 #include <queue>
 3 #include <stack>
 4 #include <cstdio>
 5 #include <vector>
 6 #include <map>
 7 #include <set>
 8 #include <bitset>
 9 #include <algorithm>
10 #include <cmath>
11 #include <cstring>
12 #include <cstdlib>
13 #include <string>
14 #include <sstream>
15 #include <time.h>
16 #define x first
17 #define y second
18 #define pb push_back
19 #define mp make_pair
20 #define lson l,m,rt*2
21 #define rson m+1,r,rt*2+1
22 #define mt(A,B) memset(A,B,sizeof(A))
23 #define mod 1000000007
24 using namespace std;
25 typedef long long LL;
26 const double PI = acos(-1);
27 const int N=1e5+10;
28 const int inf = 0x3f3f3f3f;
29 const LL INF=0x3f3f3f3f3f3f3f3fLL;
30 char s[N];
31 int a[N],b[N];
32 LL dp[N],ans=1;
33 int main()
34 {
35 #ifdef Local
36     freopen("data.txt","r",stdin);
37 #endif
38     int n,h,i,j,MAX=-inf,MIN=inf;
39     cin>>n;
40     scanf("%s",s);
41     h=strlen(s);
42     mt(dp,0);dp[0]=1;mt(b,0);
43     for(int i=0;i<26;i++)cin>>a[i];
44     for(i=1;i<=h;i++)
45     {
46         int l=inf;
47         for(j=i-1;j>=0;j--)
48         {
49             l=min(l,a[s[j]-‘a‘]);
50             if(l<(i-j))
51             {
52                 break;
53             }
54             else dp[i]=(dp[i]+dp[j])%mod;
55         }
56         MAX=max(MAX,i-j-1);
57         b[i]=b[j+1]+1;
58     }
59     cout<<dp[h]<<endl<<MAX<<endl<<b[h]<<endl;
60 #ifdef Local
61     cerr << "time: " << (LL) clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
62 #endif
63 }