Raslboyy

1420

Sep 15th, 2019
156
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.74 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <string>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. int main() {
  10.     ifstream fin("input.txt");
  11.     ofstream fout("output.txt");
  12.  
  13.     const int INF = 1e9;
  14.     string strA, strB;
  15.     fin >> strA;
  16.     int nA = strA.size();
  17.     int nB = 3;
  18.     strA += 'A';
  19.     strB = "sisA";
  20.     vector<vector<int>> dp(nA + 2, vector<int>(nB + 2, INF));
  21.     dp[0][0] = 0;
  22.     for (int i = 0; i <= nA; i++)
  23.         for (int j = 0; j <= nB; j++) {
  24.             if (strA[i] == strB[j])
  25.                 dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j]);
  26.             for (int k = i + 1; k <= nA; k++)
  27.                 dp[k][j] = min(dp[k][j], dp[i][j] + 1);
  28.         }
  29.    
  30.     fout << (dp[nA][3] == INF ? -1 : dp[nA][3]) << endl;
  31.  
  32.  
  33.     fin.close();
  34.     fout.close();
  35.     return 0;
  36. }
Advertisement
Add Comment
Please, Sign In to add comment