main.cpp (2000B)
1 #include <vector> 2 #include <iostream> 3 4 // the state is as follows: 5 // 6 // - s(fvc,oc,svc) 7 // - fvc == first v count (0->2) 8 // - oc == o count (0->1) 9 // - svc == second v count (0->2) 10 // - s(ct) 11 // - ct ranges from 0->5 12 // - vv o vv 13 // - when ct == 5, we have found one 14 // - when ct == 4 or 3, we can take a 4 15 // - ... 16 // 17 // this gives us an upper bound of 5 * size which is at worst 500_000, a reasonable number of stated assuming limited computation per state 18 19 using namespace std; 20 21 long long solve(string& input, char found, int idx, vector<vector<long long>>& memo) { 22 23 if(found == 5) { 24 return 1; 25 } 26 27 if(idx == input.size()) { 28 return 0; 29 } 30 31 if(memo[found][idx] != -1) { 32 return memo[found][idx]; 33 } 34 35 36 long long res = 0; 37 38 // we may only use v's that are adjacent 39 // if the prior was a v, but current isn't, we skip 40 if(found != 1 && found != 4) { 41 res += solve(input, found, idx+1, memo); 42 } 43 44 char current = input[idx]; 45 46 switch (found) { 47 case 0: 48 if(current == 'v') { 49 res += solve(input,found+1, idx+1, memo); 50 } 51 break; 52 case 1: 53 if(current == 'v') { 54 res += solve(input,found+1, idx+1, memo); 55 } 56 break; 57 case 2: 58 if(current == 'o') { 59 res += solve(input,found+1, idx+1, memo); 60 } 61 break; 62 case 3: 63 if(current == 'v') { 64 res += solve(input,found+1, idx+1,memo); 65 } 66 break; 67 case 4: 68 if(current == 'v') { 69 res += solve(input,found+1, idx+1,memo); 70 } 71 break; 72 } 73 74 memo[found][idx] = res; 75 return res; 76 } 77 78 int main() { 79 string input; 80 cin >> input; 81 82 vector<vector<long long>> memo (5, vector<long long> (input.size(), -1)); 83 84 cout << solve(input,0,0, memo) << endl; 85 }