fork download
copy 
  1.     #include <iostream>
  2.     #include <vector>
  3.     #include <string>
  4.  
  5.     using namespace std;
  6.  
  7.     class PartitionCounter {
  8.         // Return the number of subsequences of the suffix of v beginning at position k
  9.     	// that are (a) valid, given that the initial depth of the subsequence is d (on
  10.     	// account of it being the suffix of some larger subsequence), and (b)
  11.     	// leave behind a remainder subsequence that is also valid, given that
  12.     	// the remainder sequence has initial depth depths[k]-d.
  13.     	int count(int d, int k) {
  14.     		// If a prefix of either sequence (selected or remaining) has more ']'s
  15.     		// than '['s then there can't be any completing subsequences.
  16.     		if (d < 0 || depths[k] - d < 0) {
  17.     			return 0;
  18.     		}
  19.  
  20.     		// Only compute the answer if we haven't already.
  21.     		if (memo[d][k] == -1) {
  22.     			// A subsequence must either contain no elements, or a leftmost element
  23.     			// at some position.  All subsequences produced by recursion after this
  24.     			// initial choice are distinct (when considering the sequence of
  25.     			// character indices included, though not necessarily when considering
  26.     			// the sequence of characters themselves).
  27.  
  28.     			// Try including no elements.  This effectively terminates the larger
  29.     			// subsequence that the selected subsequence is part of, so it can be
  30.     			// legal only if its depth is 0.  It also effectively includes all
  31.     			// remaining characters in the remainder sequence, but if the selected
  32.     			// subsequence has depth 0 and the original string does too, then it's
  33.     			// implied that the remainder must also have total depth 0, so we don't
  34.     			// need to check it.
  35.     			int n = (d == 0);
  36.  
  37.     			// Try including a leftmost element at each remaining position.
  38.         		// If this would cause a remainder subsequence that has negative
  39.     			// depth, stop: any later loop iterations would also create illegal
  40.     			// remainder subsequences.
  41.     			//for (int i = k; i < v.size(); ++i) {
  42.     			for (int i = k; i < v.size() && depths[i] - d >= 0; ++i) {
  43.     				n += count(d + v[i], i + 1);
  44.     			}
  45.  
  46.     			memo[d][k] = n;
  47.     		}
  48.  
  49.     		return memo[d][k];
  50.     	}
  51.  
  52.     	vector<int> v;			// 1 for '[', -1 for ']'
  53.     	vector<int> depths;		// depths[i] is the sum of the 1st i elements
  54.     	vector<vector<int> > memo;	// DP matrix.  -1 => not computed yet
  55.  
  56.     public:
  57.     	PartitionCounter(string s) : memo(s.size() / 2 + 1, vector<int>(s.size() + 1, -1)) {
  58.     		depths.push_back(0);
  59.     		int total = 0;
  60.     		for (int i = 0; i < s.size(); ++i) {
  61.     			v.push_back(1 - 2 * (s[i] == ']'));	// Map '[' to 1 and ']' to -1
  62.     			depths.push_back(total += v[i]);
  63.     		}
  64.     	}
  65.  
  66.     	int count() {
  67.     		if (depths.back() == 0) {
  68.     			return count(0, 0);
  69.     		} else {
  70.     			return 0;		// Need to handle invalid strings specially
  71.     		}
  72.     	}
  73.     };
  74.  
  75.     int main(int argc, char **argv) {
  76.     	PartitionCounter c("[][[[[[][][][][[][][]]]]]][]");
  77.     	cout << c.count() << '\n';
  78.     }
  79.  
Success #stdin #stdout 0.02s 2820KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10001208
https://ideone.com/Xd0RnQ
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!