Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- const int MX=2e3+6;
- int n,ar[33], dp[MX],dp2[MX];
- string a;
- int MD=1e9+7,ans2=0;
- int solve(int x)
- {
- if(dp[x]!=-1)return dp[x];
- int vis[33];
- memset(vis,0,sizeof vis);
- if(x==n){
- return 1;}
- int ans=0;
- //string temp;
- for(int i=x;i<n;i++)
- {
- bool y=1;
- vis[a[i]-'a']++;
- for(int j=0;j<26;j++)
- {
- //cout<<ar[j]<<' '<<i-x+1<<' '<<j<<' '<<vis[j]<<endl;
- if(!vis[j])continue;
- if(ar[j]<i-x+1)
- y=0;
- }
- if(!y)break;
- //cout<<y<<' ';
- // if(temp=="aab")cout<<y<<' ';
- // vr.push_back(temp);
- ans2=max(ans2,i-x+1);
- ans+=solve(i+1);
- ans%=MD;
- // vr.pop_back();
- }
- return dp[x]= ans;
- }
- int solve2(int x)
- {
- if(dp2[x]!=-1)return dp2[x];
- int vis[33];
- memset(vis,0,sizeof vis);
- if(x==n){
- return 0;
- }
- int ans=1e6 ;
- for(int i=x;i<n;i++)
- {
- bool y=1;
- vis[a[i]-'a']++;
- for(int j=0;j<26;j++)
- {
- if(!vis[j])continue;
- if(ar[j]<i-x+1)
- y=0;
- }
- if(!y)break;
- ans=min(1+solve2(i+1),ans);;
- }
- return dp2[x]= ans;
- }
- int main()
- {
- memset(dp,-1,sizeof dp);
- memset(dp2,-1,sizeof dp2);
- cin>>n>>a;
- for(int i=0;i<26;i++)
- {
- cin>>ar[i];
- }
- cout<<solve(0)<<endl;
- cout<<ans2<<endl;
- cout<<solve2(0);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement