看到同机房的好哥们发了贪心做法的题解，心血来潮就A了这道题写了真·dp的题解。
虽然方法比老师上课讲的麻烦的多，并不是最优解，但至少是我自己思考得出的结果。
题目要求
输入一个原序列 \(a_i\)，从 \(a_i\) 中求得某个区间 \([l,r]\)。
此区间经过题面中所描述的修改操作（任何元素 \(+1\) 或不变），使得其中所有元素 $a_l,\dots,a_r $ 所能表示的所有数值，应当是一段连续的数值。
例如， \(4, 5, 6, 7\) 即为一段连续的数值，\(4, 6, 7\) 则不是。
此区间 \([l,r]\) 能够表示的数值种类 \(x_{\max}\) 是从 \(a_i\) 中所有区间经过修改能表示的数值种类 \(x\) 的最大值。
求这个最大的数值种类 \(x_{\max}\)。
Step.1\(\;\)分段
思路
由题易知，原序列 \(a_i\) 由若干个能够表示连续数值的序列 \(b_i\) 拼合而成。
我们最终求得的区间，必然是由原序列 \(a_i\) 中连续的几段 \(b_i\)，经过修改，拼合而成。
因此，我们首先要将原序列 \(a_i\) 分成若干段，每一段中元素所能表示的数值，是一段连续数值。
例如，样例1给出的序列：
\[1, 1, 3, 4, 6, 6, 6, 8, 10 \]经过分段得到：
\[(1,1),\,(3, 4),\,(6, 6, 6),\,(8),\,(10) \]代码实现（可以跳过）
我们用结构体 block 来存储每一段的信息。
block.length 为这一段能够表示的数值种类。
block.first 为这一段能够表示的最小值，即这一段的第一个数。
block.last 为最大值。
block.yep 数据类型为 bool，表示这一段能表示的数值能否往后延伸一位，即 这一段中有无数值在序列 \(a_i\) 中个数大于 \(1\)。
其实 block.length = block.last - block.first + 1，即block.length 可以用 block.first 和 block.last 表示。不过结构体里边开一个 block.length 写代码的时候更方便一点。
因为 \(1 \le a_i \le 10^6\)，所以我们可以用一个数组 \(cnt_a\) 来存储数字 \(a\) 在原序列中的个数。
将 \(a_i\) 储存入 \(cnt_a\) 之后，遍历 \(cnt_a\)，即可进行分段。
完整实现放在题解最后面。
Step.2\(\;\)状态转移
思路
\(dp_i\) 表示，以第 \(i\) 段为结尾，拼合的区间能表示的最大数值种类为 \(dp_i\) 种。
显然，对于每个 \(dp_i\)，初始状态为
\(dp_i = vec_{i_{last}} - vec_{i_{first}}+1\)，即第 \(i\) 个段 不修改 所能够表示的连续数值的个数。\(vec\) 是用来存储每一个的 block 信息的 vector 动态数组。
分完段之后，我们考虑，最终的区间肯定是由连续的几个 block 经过适当的修改拼合而成的。
结论1： 若两个段 block a, b 可以拼合，必然有 a.last+1 == b.first-1。
“可以拼合”是指，两个 block 表示的序列合起来所组成的序列，可以经过修改操作，表示的数值为连续数值。
例如，block a 表示的序列为 \((1, 2)\)，block b 为 \((4, 5)\)。
a.last = 2，b.first = 4，满足 a.last+1 == b.first-1。a 的两个元素均 \(+1\)，a 和 b 就可以拼合为序列 \((2, 3, 4, 5)\)。
结论2： 若多个段 block a, b, ... y, z 可以拼合，除了开始和结尾的段 block a, z，对于中间每一个段 block b, ... y 所表示的序列，必然有至少一个元素在原序列 \(a_i\) 中的个数 \(>1\)。
例如，block a, b, c 分别为 \((1,2)\)，\((4, 4, 5)\)，\((7, 8)\)。block a, b 可以拼合为 \((2, 3, 4, 4, 5)\)，这个新的序列又可以和 block c 拼合为 \((2, 3, 4, 5, 6, 7, 8)\)。中间的 block b 必然要有 \(cnt_4>1\) 或 \(cnt_5>1\)，才能让 block a, b, c 同时拼合。
根据以上两个结论，我们容易得出转移方程：
如果 \(vec_i\) 和 \(vec_{i-1}\) 两个段可以拼合，则有
\[ dp_i \gets \begin{cases} dp_{i-1} & vec_{i-1_{yep}}=1 \\ vec_{i-1_{length}} & vec_{i-1_{yep}}=0 \\ \end{cases}\]\(dp_{i-1}\) 中包含了 \(vec_{i-1}\) 之前的段的贡献。如果 \(vec_{i-1_{yep}}=0\)，即 \(vec_{i-1}\) 中所有元素个数 \(=1\)，则 \(vec_i\) 就不能与 \(vec_{i-1}\) 之前的段拼合，\(dp_i\) 只能加上 \(vec_{i-1}\) 这一段的贡献。
如果 \(vec_{i_{yep}}=1\)，则有
\[dp_i \gets dp_i+1 \]即第 \(i\) 段能表示的连续数值可以经过修改多一个。
\(vec_i\) 下标范围是 \((\,0,\,size\,)\)，\(size\) 指 \(vec\) 的大小，即 vec.size()。所以最后的答案为 \(\max(dp_i),0<i<size\)。
奉上完整实现代码：
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e6+7;
int t, n, cnt[maxn], dp[maxn];
struct block{
int length, first, last;
bool yep;
}; vector<block> vec;
int main() {
scanf("%d", &t);
while(t--) {
/*多测不清空。*/
vec.clear();
memset(dp, 0, sizeof(dp));
memset(cnt, 0, sizeof(cnt));
/*输入。*/
scanf("%d", &n); int mx;
for(int i=1; i<=n; i++) {
int a; scanf("%d", &a);
cnt[a]++;
if(i==n) mx = a;
//mx是序列a中最大的数。
}
/*分段。*/
int len=0, first=-1, last=-1; bool yep=0;
for(int i=1; i<=mx; i++) {
if (len>0 && cnt[i]==0) {
//一段结束。
last = i-1;
vec.push_back({len, first, last, yep});
yep=0; len=0;
} else if (cnt[i]>0) {
//开新一段。
if (len==0) first = i;
yep|=(cnt[i]>1); len++;
}
}
vec.push_back({len, first, mx, yep}); //加入最后一段。
/*状态转移。*/
int ans = 0;
for(int i=0; i<vec.size(); i++) {
dp[i] = vec[i].length; //初始状态。
if( i>0 && vec[i-1].last+1 == vec[i].first-1 ) {
if(vec[i-1].yep) dp[i] += dp[i-1];
else {
dp[i] += vec[i-1].length;
}
}
if(vec[i].yep) dp[i]+=1;
ans = max(ans, dp[i]);
}
printf("%d\n", ans); //输出。
}
return 0;
}
结语
这篇题解好长啊，实际上不是很麻烦的东西搞得看起来好麻烦。
这是我第一次写题解。希望大家多多包涵。
标签：block,题解,II,拼合,vec,CF1769C2,yep,dp,first From： https://www.cnblogs.com/some-side/p/17563440.html