Advertisement
jeff69

Untitled

Feb 7th, 2017
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.54 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int MX=2e3+6;
  4. int n,ar[33], dp[MX],dp2[MX];
  5. string a;
  6. int MD=1e9+7,ans2=0;
  7. int solve(int x)
  8. {
  9. if(dp[x]!=-1)return dp[x];
  10. int vis[33];
  11. memset(vis,0,sizeof vis);
  12. if(x==n){
  13. return 1;}
  14. int ans=0;
  15. //string temp;
  16. for(int i=x;i<n;i++)
  17. {
  18.  
  19. bool y=1;
  20. vis[a[i]-'a']++;
  21.  
  22. for(int j=0;j<26;j++)
  23. {
  24. //cout<<ar[j]<<' '<<i-x+1<<' '<<j<<' '<<vis[j]<<endl;
  25. if(!vis[j])continue;
  26. if(ar[j]<i-x+1)
  27. y=0;
  28.  
  29. }
  30. if(!y)break;
  31. //cout<<y<<' ';
  32. // if(temp=="aab")cout<<y<<' ';
  33. // vr.push_back(temp);
  34. ans2=max(ans2,i-x+1);
  35.  
  36. ans+=solve(i+1);
  37. ans%=MD;
  38. // vr.pop_back();
  39. }
  40. return dp[x]= ans;
  41. }
  42. int solve2(int x)
  43. {
  44. if(dp2[x]!=-1)return dp2[x];
  45. int vis[33];
  46. memset(vis,0,sizeof vis);
  47. if(x==n){
  48. return 0;
  49. }
  50. int ans=1e6 ;
  51. for(int i=x;i<n;i++)
  52. {
  53. bool y=1;
  54. vis[a[i]-'a']++;
  55. for(int j=0;j<26;j++)
  56. {
  57. if(!vis[j])continue;
  58. if(ar[j]<i-x+1)
  59. y=0;
  60. }
  61. if(!y)break;
  62. ans=min(1+solve2(i+1),ans);;
  63. }
  64. return dp2[x]= ans;
  65. }
  66. int main()
  67. {
  68. memset(dp,-1,sizeof dp);
  69. memset(dp2,-1,sizeof dp2);
  70.  
  71. cin>>n>>a;
  72. for(int i=0;i<26;i++)
  73. {
  74. cin>>ar[i];
  75. }
  76. cout<<solve(0)<<endl;
  77. cout<<ans2<<endl;
  78. cout<<solve2(0);
  79. return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement