Untitled

unknown
plain_text
a year ago
1.8 kB
1
Indexable
Never
```#define _CRT_SECURE_NO_WARNINGS
#include <functional>
#include <algorithm>
#include <iostream>
#include <memory.h>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <assert.h>
#include <bitset>
#include <string>
#include <cstdio>
#include <math.h>
#include <complex>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <set>
#include <bitset>
#include <map>
using namespace std;

#define ll long long
#define mp make_pair
#define pb push_back

typedef pair<int, int> pii;

#ifdef _DEBUG
const int N = 100;
#else
const int N = 5010;
#endif

const int MOD = 1e9+7;

int n;
int dp[N][N];
int f[N][3];
string s;

int solve(int i, int j) {
if (dp[i][j] != -1) return dp[i][j];
if (i > n && j > n) {
return dp[i][j] = 1;
}
int posM, posW, posU;
posU = f[max(i, j)][2];
posM = min(f[i][0], posU);
posW = min(f[j][1], posU);
if (posM == posW) dp[i][j] = solve(posM + 1, posW + 1);
else {
dp[i][j] = 0;
if (posM != n) dp[i][j] += solve(posM + 1, posW);
if (posW != n) dp[i][j] += solve(posM, posW + 1);
if (dp[i][j] >= MOD) dp[i][j] -= MOD;
}
return dp[i][j];
}

int main()
{
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
cin >> n;
cin >> s;
f[n][0] = f[n][1] = f[n][2] = n;
for (int i = n - 1; i >= 0; i--) {
f[i][0] = f[i + 1][0];
f[i][1] = f[i + 1][1];
f[i][2] = f[i + 1][2];
if (s[i] == 'M') f[i][0] = i;
else if (s[i] == 'W') f[i][1] = i;
else f[i][2] = i;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) dp[i][j] = -1;
}
cout << solve(0, 0);
return 0;
}```