Advertisement
erek1e

IOI '07 P4 - Miners

Jun 26th, 2022
681
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const int INF = 1e9;
  8.  
  9. int countUnique(int a, int b, int c) {
  10.     if (a==3) a=c;
  11.     if (b==3) b=c;
  12.     if (a==b && b==c) return 1;
  13.     if (a==b || b==c || a==c) return 2;
  14.     return 3;
  15. }
  16.  
  17. int main() {
  18.     int n; string s;
  19.     cin >> n >> s;
  20.     for (char &c : s) {
  21.         if (c == 'M') c = '0';
  22.         else if (c == 'F') c = '1';
  23.         else c = '2';
  24.     }
  25.  
  26.     int dp[4][4][4][4]{}; // prev1, prevprev1, prev2, prevprev2
  27.     // 3 means no set value (not enough in group)
  28.     fill_n(dp[0][0][0], sizeof(dp)/sizeof(dp[0][0][0][0]), -INF);
  29.     dp[3][3][3][3] = 0;
  30.  
  31.     for (int i = 1; i <= n; ++i) {
  32.         int dp2[4][4][4][4]{};
  33.         fill_n(dp2[0][0][0], sizeof(dp2)/sizeof(dp2[0][0][0][0]), -INF);
  34.  
  35.         int nxt = s[i-1]-'0';
  36.         for (int p1 = 0; p1 <= 3; ++p1) {
  37.             for (int pp1 = 0; pp1 <= 3; ++pp1) {
  38.                 for (int p2 = 0; p2 <= 3; ++p2) {
  39.                     for (int pp2 = 0; pp2 <= 3; ++pp2) {
  40.                         // next -> 1
  41.                         dp2[p1][nxt][pp2][p2] = max(dp2[p1][nxt][pp2][p2], dp[pp1][p1][pp2][p2] + countUnique(pp1, p1, nxt));
  42.  
  43.                         // next -> 2
  44.                         dp2[pp1][p1][p2][nxt] = max(dp2[pp1][p1][p2][nxt], dp[pp1][p1][pp2][p2] + countUnique(pp2, p2, nxt));
  45.                     }
  46.                 }
  47.             }
  48.         }
  49.         copy(begin(dp2[0][0][0]), end(dp2[3][3][3]), begin(dp[0][0][0]));
  50.     }
  51.     cout << *max_element(begin(dp[0][0][0]), end(dp[3][3][3])) << endl;
  52.     return 0;
  53. }
Advertisement
RAW Paste Data Copied
Advertisement