c++ - 动态规划 : Count how many ascending subsets exists in a set

Question

问题是:

Given an integer n and an array v of n integers, count how many ascending subsets can be formed with these numbers.

有一些限制:

• 1 ≤ n ≤ 300
• v[i] ≤ 1.000.000, whatever 1 ≤ i ≤ n
• S ≤ 10^18

例如，这里有一个例子:

Input :
6
5 2 6 1 1 8

Output:
15

解释:有 15 个升序子集。 {5}, {2}, {6}, {1}, {1}, {8}, {5, 6}, {5, 8}, {2, 6}, {2, 8}, {6 , 8}, {1, 8}, {1, 8}, {5, 6, 8}, {2, 6, 8}。

我把这个问题作为作业。我搜索了堆栈溢出、数学堆栈等，但找不到任何想法。

如果您能给我提示如何解决这个问题，那将非常有帮助。

编辑: 所以我想出了这个解决方案，但显然它在某处溢出了？你能帮帮我吗

#include <iostream>
#include <fstream>
#include <queue>

using namespace std;
ifstream fin("nrsubsircresc.in");
ofstream fout("nrsubsircresc.out");

int v[301];
int n;
long long s;

queue <int> Coada;

int main()
{
    fin >> n;
    for(int i = 0; i < n; i++)
    {
        fin >> v[i]; // reading the array
        s++;
        Coada.push(i);
    }
    while(!Coada.empty()) // if the queue is not empty
    {
        for(int k = Coada.front() + 1; k < n; k++) //
            if( v[k] > v[Coada.front()] )
            {
                s++;
                Coada.push(k);
            }
        Coada.pop();
    }
    fout << s;
    return 0;
}

Answer 1

我在这里实现了贪婪的方法:

#include <algorithm>
#include <vector>
#include <array>

using namespace std;
using ll = long long;

const int N = 6;
array<int, N> numbers = { 5, 2, 6, 1, 1, 8 }; // provided data

vector<ll> seqends(N);
int main() {
    for (int i = 0; i < N; ++i) {
        // when we adding new number to subarray so far,
        // we add at least one ascending sequence, which consists of this number
        seqends[i] = 1;
        // next we iterate via all previous numbers and see if number is less than the last one,
        // we add number of sequences which end at this number to number of sequences which end at the last number
        for (int j = 0; j < i; ++j) {
            if (numbers[j] < numbers[i]) seqends[i] += seqends[j];
        }
    }

    // Finally we sum over all possible ends
    ll res = accumulate(seqends.cbegin(), seqends.cend(), (ll)0);
    cout << res;
}

该算法需要O(N)空间和O(N²)时间。