外贸网站建设需要注意事项,微网站平台建设方案,定制手机软件,php的网站模板文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴区间DPUnique函数一、题目
1、原题链接 3996. 涂色 2、题目描述 有 n 个砖块排成一排#xff0c;从左到右编号为 1∼n。 其中#xff0c;第 i 个砖块的初始颜色为 ci。 …
文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴区间DPUnique函数一、题目
1、原题链接 3996. 涂色 2、题目描述 有 n 个砖块排成一排从左到右编号为 1∼n。 其中第 i 个砖块的初始颜色为 ci。 我们规定如果编号范围 [i,j] 内的所有砖块的颜色都相同且当第 i−1 和 第 j1 个砖块存在时这两个砖块的颜色和区间 [i,j] 的颜色均不同, 则砖块 i 和 j 属于同一个连通块。 例如[3,3,3] 有 1 个连通块[5,2,4,4] 有 3 个连通块。 现在要对砖块进行涂色操作。 开始所有操作之前你需要任选一个砖块作为起始砖块。 每次操作 任选一种颜色。将最开始选定的起始砖块所在连通块中包含的所有砖块都涂为选定颜色 请问至少需要多少次操作才能使所有砖块都具有同一种颜色。 输入格式 第一行包含整数 n。 第二行包含 n 个整数 c1,c2,…,cn。 输出格式 一个整数表示所需要的最少操作次数。 数据范围 前六个测试点满足1≤n≤20。 所有测试点满足1≤n≤50001≤ci≤5000。 输入样例1 4
5 2 2 1输出样例1 2输入样例2 8
4 5 2 2 1 3 5 5输出样例2 4输入样例3 1
4输出样例3 0输入样例4 5
1 3 1 2 1输出样例4 3样例4解释 注意每次染色操作所涉及的连通块必须包含所有操作开始前选定的起始砖块。 因此答案是 3而不是 2。 二、解题报告
1、思路分析 思路来源y总讲解视频 y总yyds 1因为每次都是改变起始点所在的连通块所以颜色相同的砖块一定是一起改变的所以我们可以先将原序列中颜色相同的砖块简化成一个砖块。 2 dp[i][j]表示所有在[i,j]中选择起点并且将[i,j]的所有砖块染成同一种颜色的所有方案数中的最小操作次数。 根据第i个砖块和第j个砖块颜色是否相同进行划分 ①第i个砖块和第j个砖块颜色不同 最后染色的为i即先求出[i1,j]染成相同颜色的最小操作次数即dp[i1][j]再加一次即将i染成与[i1,j]相同的颜色最小操作次数即为dp[i1][j]1。最后染色的砖块为j同理最小操作次数为dp[i][j-1]1。 ②第i个砖块和第j个砖块颜色相同 先将[i,j-2]染成相同颜色再将j-1和[i,j-2]染成相同颜色最后将j和[i,j-1]染成相同颜色由于该方案是在dp[i][j-1]中的某些方案也就是其子集所以将[i,j-1]染成相同颜色的操作数是大于等于dp[i][j-1]。即总操作次数大于等于dp[i][j-1]1。先将[i1,j-1]染成相同颜色再将i和[i1,j-1]染成相同颜色最后将j和[i,j-1]染成相同颜色即ij最后染色即总操作次数为dp[i1][j-1]1。由于第二种情况操作的区间比第一种情况操作的区间要短所以可知上述两种情况的最小操作次数为dp[i1][j-1]1。 综合上面三种情况即第i个砖块和第j个砖块颜色不同时dp[i][j]min(dp[i1][j]1,dp[i][j-1]1否则第i个砖块和第j个砖块颜色相同时dp[i][j]dp[i1][j-1]1。
3利用上述思路输出dp[1][n]即为答案。
2、时间复杂度
时间复杂度为O(n2)
3、代码详解
#include iostream
#include algorithm
using namespace std;
const int N5010;
int c[N],dp[N][N];
int n;
int main(){cinn;for(int i1;in;i) cinc[i];nunique(c1,cn1)-(c1); //对数组去重即合并颜色相同的砖块//枚举所有可能的区间长度for(int len2;lenn;len){for(int i1;ilen-1n;i){int jilen-1;//i和j颜色不同时的转移方程if(c[i]!c[j]) dp[i][j]min(dp[i][j-1],dp[i1][j])1;//i和j颜色相同时的转移方程else dp[i][j]dp[i1][j-1]1;}}coutdp[1][n];return 0;
}三、知识风暴 区间DP Unique函数 在头文件#include algorithm中包含。作用对数组的相邻重复元素去重并返回去重之后数组的尾地址一般用unique的返回值减去数组的首地址来求去重后数组的元素个数如果重复元素不相邻的话一般要先对原数组进行排序操作。
