链接:

https://codeforces.com/contest/1215/problem/B

题意:

You are given a sequence a1,a2,…,an consisting of n non-zero integers (i.e. ai≠0).

You have to calculate two following values:

the number of pairs of indices (l,r) (l≤r) such that al⋅al+1…ar−1⋅ar is negative;

the number of pairs of indices (l,r) (l≤r) such that al⋅al+1…ar−1⋅ar is positive;

思路:

DP[i][0]为i位置往前连续的负数, DP[i][1] 为偶数.

最后累计一下.

代码:

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAXN = 2e5+10;

int a[MAXN];

LL Dp[MAXN][2];

int n;

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    cin >> n;

    for (int i = 1;i <= n;i++)

        cin >> a[i];

    if (a[1] > 0)

        Dp[1][1] = 1;

    else

        Dp[1][0] = 1;

    for (int i = 2;i <= n;i++)

    {

        if (a[i] > 0)

        {

            Dp[i][1]++;

            Dp[i][0] += Dp[i-1][0];

            Dp[i][1] += Dp[i-1][1];

        }

        else

        {

            Dp[i][0]++;

            Dp[i][0] += Dp[i-1][1];

            Dp[i][1] += Dp[i-1][0];

        }

    }

    LL sum1 = 0, sum2 = 0;

    for (int i = 1;i <= n;i++)

        sum1 += Dp[i][0], sum2 += Dp[i][1];

    cout << sum1 << ' ' << sum2 << endl;

    return 0;

}

巴特西

Codeforces Round #585 (Div. 2) B. The Number of Products(DP)

链接:

题意:

思路:

代码:

最新文章

热门文章