递增四元组

解法：

首先都可以想到dp[i]：第i个元素结尾的递增四元组有dp[i]个

然后发现有一组数据：2,3,6,1,5,8。会出现6结尾和5结尾的递增三元组，也就是未来的决策受过去影响，专业的说就是有后效性。需要强化约束条件，于是使用dp[i][j]。

第i个元素结尾的递增j元组有dp[i][j]个，显然每个元素自身就是一个一元组，dp[i][0]=1.

对于第i个元素，若存在a[k]<a[i]，那么就可以把a[i]加在a[k]结尾的j元组，构成j+1元组。

迭代完善dp数组即可。

见例图：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define endl '\n'
const int N = 1e3 + 3;
int dp[N][4];
int main() {
	int n; cin >> n;
	vector<int> vec(n);
	for (int i = 0; i < n; i++) cin >> vec[i];
	for (int i = 0; i < n; i++) {
		dp[i][0] = 1;
		for (int j = 1; j<4; j++) {
			for (int k = 0; k < i; k++) {
				if (vec[i] > vec[k])
					dp[i][j] += dp[k][j - 1];
			}
		}
	}
	int sum = 0;
	for (int i = 0; i < n; i++) {
		sum += dp[i][3];
		sum %= 3344;
	}
	cout << sum << endl;
	
	return 0;
}