jhabar

Evaluation expression to true using DP

Dec 1st, 2020 (edited)
769
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. #define REP(i, u, v, inc) for(i=u; i<v; i += inc)
  5.  
  6. int dp(string str, int size, int i, int j, int isTrue, int mem[][101][2]) {
  7.    if(i > j) return false;
  8.     if(i == j){
  9.         if(isTrue){
  10.             return 'T' == str[i];
  11.         }
  12.         else {
  13.             return 'F' == str[i];
  14.         }
  15.     }
  16.    
  17.     if(mem[i][j][isTrue] != -1) return mem[i][j][isTrue];
  18.     int k;
  19.     int ans = 0;
  20.     REP(k, i + 1, j, 2) {
  21.         int lt, lf, rt, rf;
  22.         if(mem[i][k - 1][0] != -1){
  23.             lf = mem[i][k - 1][0];
  24.         }
  25.         else {
  26.             mem[i][k - 1][0] = lf = dp(str, size, i, k - 1, 0, mem);
  27.         }
  28.        
  29.         if(mem[i][k - 1][1] != -1){
  30.             lt = mem[i][k - 1][1];
  31.         }
  32.         else {
  33.             mem[i][k - 1][1] = lt = dp(str, size, i, k - 1, 1, mem);
  34.         }
  35.        
  36.         if(mem[k + 1][j][0] != -1){
  37.             rf = mem[k + 1][j][0];
  38.         }
  39.         else {
  40.             mem[k + 1][j][0] = rf = dp(str, size, k + 1, j, 0, mem);
  41.         }
  42.        
  43.         if(mem[k + 1][j][1] != -1){
  44.             rt = mem[k + 1][j][1];
  45.         }
  46.         else {
  47.             mem[k + 1][j][1] = rt = dp(str, size, k + 1, j, 1, mem);
  48.         }
  49.        
  50.         if(str[k] == '|') {
  51.             if(isTrue) {
  52.                 ans += (lt * rt + lt * rf + lf * rt);
  53.             } else {
  54.                 ans += (rf * lf);
  55.             }
  56.         }
  57.        
  58.         if(str[k] == '&') {
  59.             if(!isTrue) {
  60.                 ans += (lf * rf + lt * rf + lf * rt);
  61.             } else {
  62.                 ans += (rt * lt);
  63.             }
  64.         }
  65.         if(str[k] == '^') {
  66.             if(isTrue) {
  67.                 ans += (lt * rf + lf * rt);
  68.             } else {
  69.                 ans += (rt * lt + lf * rf);
  70.             }
  71.         }
  72.         if( ans < 1003) {}
  73.         else
  74.             ans %= 1003;
  75.     }
  76.     return ans;
  77. }
  78. int main() {
  79.     //code
  80.     ios::sync_with_stdio(false);
  81.     cin.tie(NULL);
  82.    
  83.     int t;
  84.     cin >> t;
  85.    
  86.     while(t--) {
  87.         int n, i, j;
  88.         cin >> n;
  89.         int mem[101][101][2];
  90.         REP(i, 0, 101, 1)
  91.             REP(j, 0, 101, 1)
  92.                 mem[i][j][0] = mem[i][j][1] = -1;
  93.                
  94.         string str;
  95.        
  96.         cin >> str;
  97.        
  98.                
  99.         cout << dp(str, str.length(), 0, str.length() - 1, 1, mem);
  100.        
  101.        
  102.        
  103.         if(t) cout << "\n";
  104.     }
  105.     return 0;
  106. }
RAW Paste Data