Dynamic Programming问题：统计升序子集数量及代码溢出排障求助

Hey there! Let's break down your problem and fix things step by step. First, let's address why your current code isn't working, then we'll go over a cleaner approach to count those increasing subsequences.

First: What's Wrong With Your Code? #

Your code has two critical issues:

1. Missing the Increasing Check
   The comment in your code mentions checking if v[k] > v[Coada.front()], but you never actually implemented this condition! Right now, you're counting every possible pair of elements (even non-increasing ones like {5,2}), which leads to way too many counts—so many that you hit overflow, and the result is completely wrong.

2. Overflow (a Symptom, Not the Root Cause)
   You're using long long for s, which is correct since the problem states results stay under (10^{18}) (and long long can hold up to ~(9 \times 10^{18})). The overflow happens only because your code is counting invalid subsequences, making s grow way beyond what it should.

Quick Fix for Your Code

Just add the missing condition to filter only increasing elements:

#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];
        s++;
        Coada.push(i);
    }
    while(!Coada.empty())
    {
        int current = Coada.front();
        for(int k = current + 1; k < n; k++) {
            // Add this check to ensure we only count increasing subsequences
            if(v[k] > v[current]) {
                s++;
                Coada.push(k);
            }
        }
        Coada.pop();
    }
    fout << s;
    return 0;
}

This will correctly count all valid increasing subsequences and avoid overflow (since the problem guarantees the result fits in a long long).

A Cleaner Approach: Dynamic Programming #

While your queue method works with the fix, dynamic programming (DP) is more intuitive for this problem. Here's how it works:

• Define dp[i]: The number of increasing subsequences that end with the i-th element (including the element itself).
• Initialize: Each dp[i] = 1 (every element is a subsequence of length 1).
• Fill the DP array: For each element i, iterate over all previous elements j < i. If v[j] < v[i], add dp[j] to dp[i]—this accounts for all subsequences ending at j that can be extended by i.
• Sum all dp[i]: The total number of valid increasing subsequences is the sum of all values in the DP array.

DP Code Example

#include <iostream>
#include <fstream>
using namespace std;

int main() {
    ifstream fin("nrsubsircresc.in");
    ofstream fout("nrsubsircresc.out");
    
    int n;
    fin >> n;
    long long dp[301] = {0};
    int v[301];
    
    for (int i = 0; i < n; ++i) {
        fin >> v[i];
        dp[i] = 1; // Start with the subsequence containing only the current element
        for (int j = 0; j < i; ++j) {
            if (v[j] < v[i]) {
                dp[i] += dp[j];
            }
        }
    }
    
    long long total = 0;
    for (int i = 0; i < n; ++i) {
        total += dp[i];
    }
    
    fout << total << endl;
    return 0;
}

For your sample input, this code calculates the dp array as [1, 1, 3, 1, 1, 8], summing to 15—exactly the expected output.

Why DP is Better #

• It's more readable: Each dp[i] clearly represents a meaningful value, making the logic easier to debug and modify.
• It uses the same (O(n^2)) time complexity as your queue method (perfect for (n \leq 300)) but avoids the overhead of a queue.

内容的提问来源于stack exchange，提问作者Vlad-Rares