histcat

Problem#

In order to achieve a better performance at the upcoming evening party, Xiao A, the leader of the AAA choir, needs to arrange the choir members according to their heights. Suppose there are a total of $n$ people in the choir, and the height of the $i$-th person is $h_i$ meters ($1000 \le h_i \le 2000$), and it is known that the heights of any two people are different. Assume the final arrangement consists of $A$ people standing in a row. To simplify the problem, Xiao A devised the following queuing method: he lets everyone stand in an initial arrangement in any order, and then inserts each person into the final arrangement from left to right according to the following principles:

• The first person is directly inserted into the empty current arrangement.
• For each person starting from the second, if they are taller than the person in front of them ($h$ is larger), they are inserted at the far right of the current arrangement. If they are shorter ($h$ is smaller), they are inserted at the far left of the current arrangement.

Once all $n$ people are inserted into the current arrangement, the final arrangement is obtained.

For example, if there are $6$ people standing in an initial arrangement with heights of $1850, 1900, 1700, 1650, 1800, 1750$, then Xiao A will obtain the final arrangement through the following steps:

• $1850$.
• $1850, 1900$, because $1900 > 1850$.
• $1700, 1850, 1900$, because $1700 < 1900$.
• $1650, 1700, 1850, 1900$, because $1650 < 1700$.
• $1650, 1700, 1850, 1900, 1800$, because $1800 > 1650$.
• $1750, 1650, 1700, 1850, 1900, 1800$, because $1750 < 1800$.

Thus, the final arrangement is $1750, 1650, 1700, 1850, 1900, 1800$.

Xiao A has an ideal arrangement in mind, and he wants to know how many initial arrangements can lead to the ideal arrangement.

Please output the answer modulo $19650827$.

For $100%$ of the data, $n \le 1000$, $1000 \le h_i \le 2000$.

Solution#

Why use interval dp? (Quoted from the solution)

We find that interval dp has a property—large intervals contain small intervals, and this problem fits such a property:

First, we define f[i][j] to represent the number of ways to achieve the ideal arrangement from interval i to j. The dp transition relies on the last different position, that is, whether the last number is inserted on the left or the right, but we find it difficult to transition.

Thus, we define f[0/1][i][j] to represent the number of ways to achieve the ideal arrangement from interval i to j (0 means the last number is inserted on the left, which is the i-th number, and 1 means the opposite), and then we can classify and discuss the transitions.

Code#

#include<bits/stdc++.h>

using namespace std;
const int N = 1010;
const int mod = 19650827;
int n, a[N];

int read()
{
	int f = 1, x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}

	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return f * x;
}

int f[N][N][2];

int main()
{
	n = read();
	for(int i = 1;i <= n;i++)
	{
		a[i] = read();
	}

	for(int i = 1;i <= n;i++)
	{
		f[i][i][0] = 1;
	}

	for(int L = 2;L <= n;L++)
	{
		for(int i = 1;i + L - 1 <= n;i++)
		{
			int j = i + L - 1;
		
			if(a[i + 1] > a[i])
				f[i][j][0] += f[i + 1][j][0];
			if(a[j] > a[i])
				f[i][j][0] += f[i + 1][j][1];
			if(a[i] < a[j])
				f[i][j][1] += f[i][j - 1][0];
			if(a[j - 1] < a[j])
				f[i][j][1] += f[i][j - 1][1];
			f[i][j][0] %= mod, f[i][j][1] %= mod;
		}
	}

	cout << (f[1][n][0] + f[1][n][1]) % mod;

	return 0;
}