首页 > 其他分享 >线性dp--最长上升子序列变形

线性dp--最长上升子序列变形

时间:2024-04-25 12:00:11浏览次数:26  
标签:matrix -- 个数 序列 int 答案 线性 amp dp

A Twisty Movement

洛谷链接:https://www.luogu.com.cn/problem/CF933A

codeforce链接:https://codeforces.com/problemset/problem/933/A

题面翻译

给定一个序列 A,你可以翻转其中的一个区间内的数,求翻转后的序列的最长不下降子序列的长度。(\(|A|\le 2000,1\le a_i \le 2\) )

感谢@touristWang 提供的翻译

题目描述

A dragon symbolizes wisdom, power and wealth. On Lunar New Year's Day, people model a dragon with bamboo strips and clothes, raise them with rods, and hold the rods high and low to resemble a flying dragon.

A performer holding the rod low is represented by a $ 1 $ , while one holding it high is represented by a $ 2 $ . Thus, the line of performers can be represented by a sequence $ a_{1},a_{2},...,a_{n} $ .

Little Tommy is among them. He would like to choose an interval $ [l,r] $ ( $ 1<=l<=r<=n $ ), then reverse $ a_{l},a_{l+1},...,a_{r} $ so that the length of the longest non-decreasing subsequence of the new sequence is maximum.

A non-decreasing subsequence is a sequence of indices $ p_{1},p_{2},...,p_{k} $ , such that $ p_{1}<p_{2}<...<p_{k} $ and $ a_{p1}<=a_{p2}<=...<=a_{pk} $ . The length of the subsequence is $ k $ .

输入格式

The first line contains an integer $ n $ $ (1<=n<=2000) $ , denoting the length of the original sequence.

The second line contains $ n $ space-separated integers, describing the original sequence $ a_{1},a_{2},...,a_{n} $ $ (1<=a_{i}<=2,i=1,2,...,n) $ .

输出格式

Print a single integer, which means the maximum possible length of the longest non-decreasing subsequence of the new sequence.

样例 #1

样例输入 #1

4
1 2 1 2

样例输出 #1

4

样例 #2

样例输入 #2

10
1 1 2 2 2 1 1 2 2 1

样例输出 #2

9

提示

In the first example, after reversing $ [2,3] $ , the array will become $ [1,1,2,2] $ , where the length of the longest non-decreasing subsequence is $ 4 $ .

In the second example, after reversing $ [3,7] $ , the array will become $ [1,1,1,1,2,2,2,2,2,1] $ , where the length of the longest non-decreasing subsequence is $ 9 $ .

注意:解析扒的这位佬的 https://www.luogu.com.cn/article/fv3mhsdw

分析

考虑 DP

由于序列只有两个数,那么最终的非降子序列一定是 \(\{1, 1, \dots 1, 2, 2, \dots, 2\}\) 这样的形式。可以这样表示:\([1][2]\),表示分别由 \(1\) 和 \(2\) 组成的序列。其中这两个部分可能为空。

如果翻转后得到 \([1][2]\),那么翻转前的子序列应该是 \([1][2][1][2]\) 的形式,使得交换中间两个子序列后变成非降子序列。同样的,这些序列也可以为空。

因为最多交换一次,所以题目变成了找原序列的最长子序列,且形式为 \([1][2][1][2]\)。

一共有 \(4\) 部分,分别将其标号为 \(0 \sim 3\)。设状态 \(f_{i, j}(j \in [0, 3])\) 表示序列前 \(i\) 个数中,选择前 \(j\) 个序列的最长长度。接下来考虑转移。

  • \(f_{i, 0}\),前 \(0\) 个部分:

    如果第 \(i\) 个数为 \(1\),那么可以把这个数和以前的拼起来。答案为 \(f_{i - 1, 0} + 1\)。

    否则,如果第 \(i\) 个数为 \(2\),那么这个数不可以作为第 \(0\) 部分。答案为 \(f_{i - 1, 0}\)。

    因此 \(f_{i, 0} = \left\{\begin{matrix} f_{i - 1, 0} + 1 &amp; (a_i = 1)\\ f_{i - 1, 0} &amp; (a_i = 2)\end{matrix}\right.\)。

  • \(f_{i, 1}\),前 \(1\) 个部分。

    如果第 \(1\) 个部分为空,那么答案为 \(f_{i, 0}\)。以下都是不空的情况。

    如果第 \(i\) 个数为 \(2\),那么可以把这个数和以前的拼起来。答案为 \(f_{i - 1, 1} + 1\)。

    否则,如果第 \(i\) 个数为 \(1\),那么这个数不可以作为第 \(1\) 部分。答案为 \(f_{i - 1, 1}\)。

    因此 \(f_{i, 1} = \left\{\begin{matrix} \max(f_{i, 0}, f_{i - 1, 1} + 1) &amp; (a_i = 2)\\ \max(f_{i, 0}, f_{i - 1, 1}) &amp; (a_i = 1)\end{matrix}\right.\)。

  • \(f_{i, 2}\),前 \(2\) 个部分。

    如果第 \(2\) 个部分为空,那么答案为 \(f_{i, 1}\)。以下都是不空的情况。

    如果第 \(i\) 个数为 \(1\),那么可以把这个数和以前的拼起来。答案为 \(f_{i - 1, 2} + 1\)。

    否则,如果第 \(i\) 个数为 \(2\),那么这个数不可以作为第 \(2\) 部分。答案为 \(f_{i - 1, 2}\)。

    因此 \(f_{i, 2} = \left\{\begin{matrix} \max(f_{i, 1}, f_{i - 1, 2} + 1) &amp; (a_i = 1)\\ \max(f_{i, 1}, f_{i - 1, 2}) &amp; (a_i = 2)\end{matrix}\right.\)。

  • \(f_{i, 3}\),前 \(3\) 个部分。

    如果第 \(3\) 个部分为空,那么答案为 \(f_{i, 2}\)。以下都是不空的情况。

    如果第 \(i\) 个数为 \(2\),那么可以把这个数和以前的拼起来。答案为 \(f_{i - 1, 3} + 1\)。

    否则,如果第 \(i\) 个数为 \(1\),那么这个数不可以作为第 \(3\) 部分。答案为 \(f_{i - 1, 3}\)。

    因此 \(f_{i, 3} = \left\{\begin{matrix} \max(f_{i, 2}, f_{i - 1, 3} + 1) &amp; (a_i = 2)\\ \max(f_{i, 2}, f_{i - 1, 3}) &amp; (a_i = 1)\end{matrix}\right.\)。

最后答案为 \(f_{n, 3}\)。

#include <iostream>
using namespace std;
const int N = 2010;
int a[N];
int f[N][4];
int n;

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

	for (int i = 1; i <= n; i++) 
	{

		f[i][0] = f[i - 1][0] + (a[i] == 1);
		f[i][1] = max(f[i][0], f[i - 1][1] + (a[i] == 2));
		f[i][2] = max(f[i][1], f[i - 1][2] + (a[i] == 1));
		f[i][3] = max(f[i][2], f[i - 1][3] + (a[i] == 2));
	}
	cout << f[n][3]; 
	return 0;
}

标签:matrix,--,个数,序列,int,答案,线性,amp,dp
From: https://www.cnblogs.com/xingzhuz/p/18157309

相关文章

  • python读取xls表格中指定列或行范围的数据
    importxlrd#打开Excel文件workbook=xlrd.open_workbook('test01.xls')#获取第一个工作表worksheet=workbook.sheet_by_index(0)#指定的行区域#读取第(row_index_x+1)行中,第(start_cols+1)列至第end_cols列范围的数据start_cols=0#第(start_cols+1)列end_cols......
  • 解决mysql 事务死锁的方法
    使用以下命令查看引擎的状态SHOWENGINEINNODBSTATUS; 如果有事务死锁可以看到如下图的关键字 找到上图的线程id使用kill57763.解决问题。问题回放,事务死锁如何产生?本地调试,长事务,调试至中途,断开调试,事务未提交。下次进入事务时候同样参数会触发锁。必须kill......
  • 记录一次责任链设计模式使用低级错误
    记录一次责任链设计模式使用低级错误目录记录一次责任链设计模式使用低级错误背景流程发现问题解决方案总结背景提供一个服务支持语音转写成文本,以及历史转写备份数据的简单服务。提供一个接口批量上传,一次最大1000条(分表)落库之后同时发送到消息队列并更新数据状态消费......
  • ef core 如何关联查询外键表
    在EFCore中,如果查询查询外键表的内容实体publicclassBlog{publicintBlogId{get;set;}publicstringUrl{get;set;}publicList<Post>Posts{get;set;}//集合导航属性publicList<Comment>Comments{get;set;}//集合导航属性}......
  • 【pytorch学习】之线性神经网络-图像分类数据集
    图像分类数据集MNIST数据集(LeCunetal.,1998)是图像分类中广泛使用的数据集之一,但作为基准数据集过于简单。我们将使用类似但更复杂的Fashion‐MNIST数据集(Xiaoetal.,2017)。%matplotlibinlineimporttorchimporttorchvisionfromtorch.utilsimportdatafromt......
  • day23-必备SQL和表关系及授权
    1.必备SQL语句上一节讲解了最基础SQL语句:增删改查,其实在日常的开发中还有很多必备的SQL语句。这一部分的SQL语句都是围绕着对表中的数据进行操作的。提示:今天的所有操作我都只会在MySQL自带的客户端工具上进行操作。例如:现在创建如下两张表。createdatabaseday26dbdef......
  • blog.admin 查询增加过滤器,添加、删除增加数据审计、统一控制权限操作
    一、查询增加过滤器需求说明:有几张表(医生表、病人表等),有个字段ClinicID都与诊所表主键Id关联。用户登录系统时候,根据所分配的诊所权限,只查看自己诊所的数据。通过查询过滤器,在查询每个表的时候,自动将ClinicID==当前登录用户所属ClinicID,添加上。1、创一个IClinicEntity接口usi......
  • 看基类被那几个类了
    usingSystem;usingSystem.Reflection;usingSystem.Linq;publicclassBaseClass{}publicclassDerivedClass1:BaseClass{}publicclassDerivedClass2:BaseClass{}classProgram{staticvoidMain(){TypebaseType=typeof(......
  • 【题解】A566.三点共线
    题目大意,给定在平面直角坐标系中的多个点,判断有多少个三元组\((A,B,C)\)满足共线性质。题目链接:A566.三点共线。大题思路就是暴力所有的三元组,判断三个元素的斜率是否相同即可。其实还有其他方法可以做,我个人感觉用斜率法最简单。有几点需要注意:在计算斜率的时候,如果多......
  • Git runner 返回报错: status=couldn't execute POST against dial tcp: lookup gitlab
    当发现Gitlab上的runner显示出runneroffline的问题时1查一下gitrunner的报错runner=xxxxstatus=couldn'texecutePOSTagainsthttps://gitlab/api/v4/jobs/request:Posthttps://gitlab/api/v4/jobs/request:dialtcp:lookupgitonx.x.x.x:53:servermisbehaving......