递增四元组

本文主要是介绍递增四元组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

解法：

首先都可以想到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;
}

这篇关于递增四元组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---