题解 CF1215B 【The Number of Products】
幽界の冥神
·
·
题解
这题就是一道简单DP啊，还卡我10min。
我们设f_i表示以i结尾为乘积正数的个数，g_i表示以i结尾为乘积负数的个数，我们就可以推递推式了。
$2.$ 递推：
(1)$a[i] > 0:f[i] += f[i - 1],g[i] +=g[i - 1]
(2)a[i] < 0:f[i] += g[i - 1], g[i] += f[i - 1]
解释一下：若a[i] > 0，对子串乘积的正负没有影响，反之会使子串乘积的正负正好相反，本题的转移方程就显而易见了。
上代码：
```cpp
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#define N 200005
using namespace std;
int n, a[N], pos[N], tot;
long long f[N], g[N];
int main () {
scanf ("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf ("%d", a + i);
if (a[i] > 0) f[i] = 1;
else g[i] = 1;
}
for (int i = 2; i <= n; ++i) {
if (a[i] > 0) {
f[i] += f[i - 1];
g[i] += g[i - 1];
}
else {
f[i] += g[i - 1];
g[i] += f[i - 1];
}
}
long long rg = 0, rf = 0;
for (int i = 1; i <= n; ++i) {
rf += f[i];
rg += g[i];
}
printf ("%I64d %I64d\n", rg, rf);
return 0;
}
```