网站开发的销售,有没有专门做牛仔的网站,网页制作公司 贵阳,广东长城建设集团有限公司 网站解法#xff1a;
首先都可以想到dp[i]#xff1a;第i个元素结尾的递增四元组有dp[i]个
然后发现有一组数据#xff1a;2,3,6,1,5,8。会出现6结尾和5结尾的递增三元组#xff0c;也就是未来的决策受过去影响#xff0c;专业的说就是有后效性。需要强化约束条件#xff0…
解法
首先都可以想到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元组构成j1元组。
迭代完善dp数组即可。
见例图 #includeiostream
#includealgorithm
#includevector
using namespace std;
#define endl \n
const int N 1e3 3;
int dp[N][4];
int main() {int n; cin n;vectorint 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; j4; 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;
}
