CodeStar第五周周赛

T1：复合逻辑表达式

本题难度中等，线性 \(dp\) 问题。根据最后一个运算递推：如果是 AND，需要两边都是 true；如果是 OR，只需任意一个是 true

当 S[i] = 'AND'
y[i-1]=T 且 x[i]=T: y[i] = T
y[i-1]=T 且 x[i]=F: y[i] = F
y[i-1]=F 且 x[i]=T: y[i] = F
y[i-1]=F 且 x[i]=F: y[i] = F

y[i]=T 的方案数等于 y[i-1]=T 的方案数
y[i]=F 的方案数等于 y[i-1]=F 的方案数 $\times 2 \ + $ y[i-1]=T 的方案数等于 y[i-1]=T 的方案数

令 dp[i][0] 表示 y[i]=F 的方案数，dp[i][1] 表示 y[i]=T 的方案数
转移方程：

当 s[i]='AND' 时：
\( dp[i][0] = dp[i-1][0]*2 + dp[i-1][1] \)
\( dp[i][1] = dp[i-1][1] \)

当 s[i]='OR' 时：

y[i-1]=F 且 x[i]=F: y[i] = F
y[i-1]=T 且 x[i]=F: y[i] = T
y[i-1]=F 且 x[i]=T: y[i] = T
y[i-1]=T 且 x[i]=T: y[i] = T

\( dp[i][0] = dp[i-1][0] \)
\( dp[i][1] = dp[i-1][1]*2 + dp[i-1][0] \)

答案是 \(dp[n][1]\)

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

ll dp[65][2];

int main() {
    int n;
    cin >> n;
    
    vector<string> s(n);
    rep(i, n) cin >> s[i];
    
    dp[0][0] = dp[0][1] = 1;
    rep(i, n) {
        if (s[i] == "AND") {
            dp[i+1][0] = dp[i][0]*2 + dp[i][1];
            dp[i+1][1] = dp[i][1];
        }
        else {
            dp[i+1][0] = dp[i][0];
            dp[i+1][1] = dp[i][1]*2 + dp[i][0];
        }
    }
    
    cout << dp[n][1] << '\n';
    
    return 0;
}