题解：AcWing 4918 万圣节服饰

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing4918. 万圣节服饰 - AcWing题库【题目描述】加普要在今晚依次参加N NN场万圣节变装派对编号1 ∼ N 1∼N1∼N。参加不同派对需要身着的服装样式可能不尽相同。在参加第i ii场派对时加普需要身着第c i c_ici​种样式的服装。为了圆满的参加完所有派对加普需要准备很多件衣服同一样式的衣服可能需要不止一件。在参加第一场派对前他可以事先一件套一件的穿上很多件衣服他既不怕热也不嫌难受需要的情况下套多少件都可以。此外在每场派对开始之前他可以选择脱掉若干件身上的衣服或者穿上一件新的衣服。也就是说如果他现在穿着两件衣服外面一件是服装1 11里面一件是服装2 22而接下来他要参加的派对需要身着服装2 22那么他既可以选择脱掉外面的服装1 11露出里面的服装2 22也可以选择再穿一件新的服装2 22。值得注意的是加普不会将脱下的衣服再次穿上也就是说如果他现在脱掉了一件服装1 11那么即使以后他需要再次穿上一件服装1 11他也只能找一件新的来穿而不能穿之前脱下的那件。衣服必须从外向里一件一件的脱想要脱掉里面的一件衣服就必须将其外面的衣服先脱掉。请你计算为了圆满的参加完所有派对加普至少需要准备多少件衣服。【输入】第一行包含整数T TT表示共有T TT组测试数据。每组数据第一行包含整数N NN。第二行包含N NN个整数c 1 , c 2 , … , c N c_1,c_2,…,c_Nc1​,c2​,…,cN​。【输出】每组数据输出一行结果格式为Case x: y其中x xx为组别编号从1 11开始y yy为最少需要准备的衣服数量。【输入样例】2 4 1 2 1 2 7 1 2 1 1 3 2 1【输出样例】Case 1: 3 Case 2: 4【算法标签】#区间DP【代码详解】#includebits/stdc.husingnamespacestd;constintN105;intT,n,c[N];intf[N][N];// 动态规划数组f[i][j]表示从i到j的最少染色次数intmain(){cinT;// 输入测试用例数量intt1;// 测试用例编号while(T--)// 处理每个测试用例{cinn;// 输入珠子数量memset(f,0,sizeof(f));// 初始化动态规划数组for(inti1;in;i)// 输入每个珠子的颜色{cinc[i];f[i][i]1;// 单个珠子需要染色1次}for(intlen2;lenn;len)// 枚举区间长度{for(inti1;ilen-1n;i)// 枚举区间起点{intjilen-1;// 区间终点f[i][j]f[i][j-1]1;// 先考虑单独染色最后一个珠子的情况for(intki;kj-1;k)// 寻找与最后一个珠子颜色相同的位置if(c[k]c[j])// 如果找到颜色相同的珠子f[i][j]min(f[i][j],f[i][k]f[k1][j-1]);// 更新最小值}}printf(Case %d: %d\n,t,f[1][n]);// 输出结果t;// 测试用例编号加1}return0;}【运行结果】2 4 1 2 1 2 Case 1: 3 7 1 2 1 1 3 2 1 Case 2: 4