Podeli niz

Za dati niz celih brojeva ispitati na koliko načina ga je moguće podeliti na segmente tako da svaki segment počinje i završava se brojem iste parnosti.

Opis ulaza

Sa standardnog ulaza se učitava veličina niza \(n\) (\(1 \leq n \leq 100\)), a zatim i \(n\) elemenata niza u opsegu od 0 do 100.

Opis izlaza

Primer

Ulaz

Izlaz

Objašnjenje

Rešenje

Opis glavnog rešenja

U ovom bloku se opisuje glavno rešenje zadatka.

#include <iostream>
#include <vector>

using namespace std;

/*   i : 0 1 2 3 4 5
 * a[i]: 1 2 3 4 5
 * f(i): 5 3 2 1 1 1
 * 
 * i:[0..4]      i:[1..4]   i:[2..4]    i:[3..4]    i:[4..4]    i:[5..4]
 * |1|2|3|4|5|   |2|3|4|5|  |3|4|5|     |4|5|       |5|
 * |1 2 3|4|5|   |2 3 4|5|  |3 4 5|
 * |1|2 3 4|5|   |2|3 4 5|
 * |1|2|3 4 5|
 * |1 2 3 4 5|
 */

int count_segments(vector<int> &a)
{
    const int N = a.size();

    vector<int> dp(N + 1);
    dp[N] = 1;

    int sum_even = 0, sum_odd = 0;
    for (int n = N - 1; n >= 0; n--) {
        if (a[n] % 2 == 1) { // neparni
            sum_odd += dp[n + 1];
            dp[n] = sum_odd;
        } else { // a[n] % 2 == 0, parni
            sum_even += dp[n + 1];
            dp[n] = sum_even;
        }
    }

    return dp[0];
}

int main() 
{
    int n; cin >> n;

    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }

    cout << count_segments(a) << endl;

    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

// count segments of a[i..n-1]
int count_segments(vector<int> &a, const int i)
{
    const int n = a.size();

    if (i == n) { 
        return 1; // a[n..n-1] = {} 
    }

    int count = 0;
    for (int j = i; j < n; j++) {
        if (a[i] % 2 == a[j] % 2) { 
            // mark a[i..j] and continue counting from a[j+1..n-1]
            count += count_segments(a, j + 1);
        }
    }

    return count;
}

int main() 
{
    int n; cin >> n;

    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }

    cout << count_segments(a, 0) << endl;

    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

// count segments of a[i..n-1]
int count_segments(vector<int> &a, const int i, vector<int> &memo)
{
    const int n = a.size();

    if (i == n) { 
        return memo[i] = 1; // a[n..n-1] = {} 
    }

    if (memo[i]) {
        return memo[i];
    }
 
    int count = 0;
    for (int j = i; j < n; j++) {
        if (a[i] % 2 == a[j] % 2) { 
            // mark a[i..j] and continue counting from a[j+1..n-1]
            count += count_segments(a, j + 1, memo);
        }
    }

    return memo[i] = count;
}

int count_segments(vector<int> &a)
{
    const int n = a.size();
    vector<int> memo(n + 1);
    return count_segments(a, 0, memo);
}

int main() 
{
    int n; cin >> n;

    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }

    cout << count_segments(a) << endl;

    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

/*   i : 0 1 2 3 4 5
 * f(i): 5 3 2 1 1 1
 * 
 * i:[0..4]      i:[1..4]   i:[2..4]    i:[3..4]    i:[4..4]    i:[5..4]
 * |1|2|3|4|5|   |2|3|4|5|  |3|4|5|     |4|5|       |5|
 * |1 2 3|4|5|   |2 3 4|5|  |3 4 5|
 * |1|2 3 4|5|   |2|3 4 5|
 * |1|2|3 4 5|
 * |1 2 3 4 5|
 */

int count_segments(vector<int> &a)
{
    const int N = a.size();

    vector<int> dp(N + 1);
    dp[N] = 1;

    for (int n = N - 1; n >= 0; n--) {
        int count = 0;
        for (int k = n; k < N; k++) {
            if (a[n] % 2 == a[k] % 2) {
                count += dp[k + 1];
            }
        }
        dp[n] = count;
    }


    return dp[0];
}

int main() 
{
    int n; cin >> n;

    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }

    cout << count_segments(a) << endl;

    return 0;
}