YEZAELP

PROG-2003: Miners

Jul 7th, 2020 (edited)
66
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.03 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int INF = 2e9;
  5. int n;
  6. int ar[100010];
  7. bool check[5];
  8. int dp[2][4][4][4][4];
  9.  
  10. int main(){
  11.  
  12.     scanf("%d", &n);
  13.  
  14.     for(int i=1;i<=n;i++){
  15.         char a;
  16.         scanf(" %c", &a);
  17.         if(a == 'M') ar[i] = 1;
  18.         else if(a == 'F') ar[i] = 2;
  19.         else ar[i] = 3;
  20.     }
  21.  
  22.     for(int i=n;i>=1;i--){
  23.         for(int a=0;a<=3;a++){
  24.             for(int b=0;b<=3;b++){
  25.                 for(int c=0;c<=3;c++){
  26.                     for(int d=0;d<=3;d++){
  27.                         int cnt1 = 0;
  28.                         check[a] = check[b] = check[ar[i]] = true;
  29.                         for(int j=1;j<=3;j++) {
  30.                             if(check[j]) cnt1 ++;
  31.                             check[j] = false;
  32.                         }
  33.                         int cnt2 = 0;
  34.                         check[c] = check[d] = check[ar[i]] = true;
  35.                         for(int j=1;j<=3;j++){
  36.                             if(check[j]) cnt2 ++;
  37.                             check[j] = false;
  38.                         }
  39.                         dp[i%2][a][b][c][d] = max(cnt1 + dp[(i+1)%2][b][ar[i]][c][d],
  40.                                                 cnt2 + dp[(i+1)%2][a][b][d][ar[i]]);
  41.                     }
  42.                 }
  43.             }
  44.         }
  45.     }
  46.  
  47.     printf("%d", dp[1][0][0][0][0]);
  48.  
  49.     return 0;
  50. }
  51.  
  52. /*void filled(){
  53.     for(int j=1;j<=3;j++) check[j] = false;
  54. }
  55. int f(int i, int a, int b, int c, int d){
  56.     if(i > n) return 0;
  57.     if(dp[i][a][b][c][d] != -INF) return dp[i][a][b][c][d];
  58.     // 1
  59.     int cnt1 = 0;
  60.     filled();
  61.     check[a] = true;
  62.     check[b] = true;
  63.     check[ar[i]] = true;
  64.     for(int j=1;j<=3;j++){
  65.         if(check[j]) cnt1 ++;
  66.     }
  67.     // 2
  68.     int cnt2 = 0;
  69.     filled();
  70.     check[c] = true;
  71.     check[d] = true;
  72.     check[ar[i]] = true;
  73.     for(int j=1;j<=3;j++) {
  74.         if(check[j]) cnt2 ++;
  75.     }
  76.     // recursive step
  77.     dp[i][a][b][c][d] = max(cnt1 + f(i+1, b, ar[i], c, d), cnt2 + f(i+1, a, b, d, ar[i]));
  78. }*/
RAW Paste Data Copied