看到同机房的好哥们发了贪心做法的题解,心血来潮就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给出的序列:
经过分段得到:
代码实现(可以跳过)
我们用结构体 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-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\),则有
即第 \(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;
}
结语
这篇题解好长啊,实际上不是很麻烦的东西搞得看起来好麻烦。
这是我第一次写题解。希望大家多多包涵。