递增四元组

解法:

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/479339.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

普发Pfeiffer分子泵TMH-U1001PC-1601PC安装使用维护说明

普发Pfeiffer分子泵TMH-U1001PC-1601PC安装使用维护说明

【Linux中vim系列】如何在vim中检索字符串

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

最简明的大模型agent教程

大模型相关目录 大模型&#xff0c;包括部署微调prompt/Agent应用开发、知识库增强、数据库增强、知识图谱增强、自然语言处理、多模态等大模型应用开发内容 从0起步&#xff0c;扬帆起航。 大模型应用向开发路径及一点个人思考大模型应用开发实用开源项目汇总大模型问答项目…

关闭Elasticsearch built-in security features are not enabled

禁用Kibana安全提示&#xff08;Elasticsearch built-in security features are not enabled&#xff09; Kibana提示#! Elasticsearch built-in security features are not enabled. Without authentication, your cluster could be accessible to anyone. See https://www.e…

基于SSM+Jsp+Mysql的KTV点歌系统

基于SSMJspMysql的KTV点歌系统 基于SSMJspMysql的KTV点歌系统的设计与实现 开发语言&#xff1a;Java框架&#xff1a;ssm技术&#xff1a;JSPJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工…

Redisson分布式锁(WatchDog分析,浅浅看下源码)

带大家简单了解下Redisson的看门狗机制&#xff0c;这个面试中也比较常见。 目录 WatchDog&#xff08;看门狗&#xff09;机制开启WatchDog&#xff08;看门狗&#xff09;浅看下源码 WatchDog&#xff08;看门狗&#xff09;机制 Redisson看门狗机制是用于解决在业务运行时间…

弱网测试利器 - Charles工具实战分享!

一&#xff1a;弱网测试要点 二&#xff1a;利用抓包工具charles进行弱网设置&#xff0c;适用PC端和移动端&#xff08;IOS&#xff0f;Android&#xff09; 1、以charles 4.5.6版本为例&#xff0c;打开Proxy->Throttle Settings 2、打开Throttle Settings&#xff0c;界面…

蓝桥杯练习06给网页化个妆

给页面化个妆 介绍 各个网站都拥有登录页面&#xff0c;设计一个界面美观的登录页面&#xff0c;会给用户带来视觉上的享受。本题中我们要完成一个登录页面的布局。 准备 开始答题前&#xff0c;需要先打开本题的项目代码文件夹&#xff0c;目录结构如下&#xff1a; 其中&…

A7680C 4G模块连接MQTT服务器

AT\r\n检查模块正常工作 返回 OK ATCPIN?\r\n检查SIM是否正常 返回&#xff1a; [20:01:31.561]接收←ATCPIN? CPIN: READY OK ATCGREG? //检查网络注册注册状态 返回 [20:02:21.042]接收←ATCGREG?…

28 OpenCV 轮廓周围绘制图形

文章目录 approxPolyDP 轮廓周围绘制矩形boundingRectminAreaRect绘制圆和椭圆示例 approxPolyDP 轮廓周围绘制矩形 approxPolyDP(InputArray curve, OutputArray approxCurve, double epsilon, bool closed)curve&#xff1a;输入点集&#xff0c;二维点向量的集合appro…

干货!Python正则表达式之匹配分组和其他功能函数

1.匹配分组 ()&#xff1a;表示一个整体&#xff0c;表示分组&#xff0c;然后捕获 2.匹配分组实例 # 导入re模块 import re ​ tel "0755-98776754" ​ # 定义正则表达式 pattern "(\\d{4})-(\\d{8})" result re.search(pattern, tel) print(result…

offer选择:创业公司 VS 大厂外包

面试拿到两个offer&#xff0c;一个是规模只有几十人的初创小公司&#xff0c;另一个是大厂外包岗位。都是功能测试&#xff0c;两者薪水待遇也差不多&#xff0c;该如何选择?更有利于之后的职业发展...... 这是一个比较典型的问题&#xff0c;对于要转行的同学或者是刚入行没…

Leetcode 200. 岛屿数量

心路历程&#xff1a; 在没有看图论这一章之前看这道题没什么直接的思路&#xff0c;在看完图论之后&#xff0c;学着使用DFS和BFS去套用解决。第一次自己做的时候还是遇到了很多小问题。整体思路很流畅&#xff0c;但是需要处理的细节第一次没怎么处理好&#xff0c;花了很多…

VC++ error C1001: 内部编译器错误 c\error.h”,第 1291 行) 原因和解决

原因是使用模板时实现方法没写分号 #include <iostream>template <class T> class A { public:A() {};~A() {};void GetName() {return}; };int main(int argc, char* argv[]) {return 0; }

Linux:执行命令的命令eval与Bash解析命令的方式

相关阅读 Linuxhttps://blog.csdn.net/weixin_45791458/category_12234591.html?spm1001.2014.3001.5482 eval命令用于接收参数&#xff0c;并将这些参数作为一行命令执行&#xff0c;这也许会使人困惑&#xff0c;为什么我不能直接执行命令而需要使用eval命令间接执行呢&…

【题目】【网络系统管理】2022 年全国职业院校技能大赛 网络系统管理赛项 模块 A:网络构建

2022 年全国职业院校技能大赛 网络系统管理赛项 模块 A&#xff1a;网络构建 目录 考试说明 … 3 任务描述 … 3 任务清单 … 3 &#xff08;一&#xff09;基础配置 … 3 &#xff08;二&#xff09;有线网络配置 … 4 &#xff08;三&#xff09;无线网络配置 … 5 &…

仿muduo库实现one thread one loop式并发服务器

文章目录 一、项目简介 二、项目整体认识 2、1 HTTP服务器 2、2 Reactor模型 三、预备知识 3、1 C11 中的 bind 3、2 简单的秒级定时任务实现 3、3 正则库的简单使用 3、4 通用类型any类型的实现 四、服务器功能模块划分与实现 4、1 Buffer模块 4、2 Socket模块 4、3 Channel模…

数据结构--树(二叉树)

定义 树的结点 如上图A的结点为2&#xff0c;B的结点为1&#xff0c;树的结点就是最多的那个&#xff0c;这棵树的结点就是3. 树的存储结构 树的存储结构可以是多样的 typedef struct BiTNode /* 结点结构 */ {DATATYPE data; /* 结点数据 */struct BiTNode *lchild,*rchi…

算法打卡Day14

今日任务&#xff1a; 1&#xff09;104.二叉树的最大深度 2&#xff09;559.n叉树的最大深度 3&#xff09;111.二叉树的最小深度 4&#xff09;222.完全二叉树的节点个数 104.二叉树的最大深度 题目链接&#xff1a;104. 二叉树的最大深度 - 力扣&#xff08;LeetCode&#…

视频讲解|基于非对称纳什谈判的多微网电能共享运行优化策略

1 主要内容 该讲解视频对应的程序链接为基于非对称纳什谈判的多微网电能共享运行优化策略_吴锦领&#xff0c;主要内容是对《基于非对称纳什谈判的多微网电能共享运行优化策略》的matlab复现&#xff0c;解决的是微网间基于非对称纳什谈判的P2P电能交易共享问题&#xff0c;基…