专栏文章

题解：P10977 Cut the Sequence

bbianshiyang
P10977题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqakr6c
此快照首次捕获于
2025/12/04 01:39
3 个月前
此快照最后确认于
2025/12/04 01:39
3 个月前
查看原文
题目传送门

分析

考虑本题解法，首先答案不具有单调性所以二分行不通（并不是所有的最大值最小化都可以用二分），且划分的区间数以及每段区间最大值出现的位置不易得知，故几乎无法使用贪心算法求解。发现如果只考虑最后一段划分的区间，那么其最值只与区间首尾有关，而与前面部分的划分无关，满足最优子结构的性质，考虑使用动态规划进行求解。
定义 fif_i 表示划分完前 ii 个数后每一部分的最大整数之和的最小值，以最后一段为划分依据，考虑转移：
fi=min⁡0≤j<i∧∑k=j+1iak≤m(fj+max⁡k=j+1iak)f_i=\min_{0\le j<i\wedge \sum_{k=j+1}^ia_k\le m}(f_j+\max_{k=j+1}^ia_k)
发现 max⁡\max 求解时可以在扫描的时候用一个变量 O(1)O(1) 维护。所以 DP 的复杂度为 O(n2)O(n^2)，此题无法通过，考虑优化。
我们可以尝试及时排除不必要的决策，首先考虑一个决策 jj 何时可能成为最优决策。不难发现 fif_i 呈现单调递增的趋势，即多加进来一个数，答案只会变大或者不变，否则可以用 fif_i 的划分方式更新 fi−1f_{i-1} 使其减小。所以发现如果 jj 从 i−1i-1 向前枚举，若 ∑k=j+1iak≤m\sum_{k=j+1}^ia_k\le m 条件满足且 max⁡k=j+1iak\max_{k=j+1}^ia_k 不变的话（上界已经确定，所以最大值要么增大要么不变），那么答案将会变小，也就是说取前面的 jj 一定更优，就可以排除很多决策了。
所以对于每一个 ii，我们向前找到第一个满足 aj>aia_j>a_i 的 jj，这个那么 j+1j+1 到 i−1i-1 的所有决策就都可以排除，而如果此时 jj 不满足条件 ∑k=j+1iak≤m\sum_{k=j+1}^ia_k\le m，那么我们向前找到第一个不满足条件的 jj 作为决策，也就是把 j+1j+1 到 ii 这一段划分出来。手上有蓝书的同学就会发现我们利用单调性推导出了书中 jj 需要至少满足一项的两个条件（而非先猜后证）：
  1. aj=max⁡k=jiaka_j=\max_{k=j}^ia_k，即 jj 是第一个满足 aj>aia_j>a_i 的。
  2. ∑k=j+1iak>m\sum_{k=j+1}^ia_k> m，即 jj 是第一个不满足 ∑k=j+1iak≤m\sum_{k=j+1}^ia_k\le m 的。
所以我们可以利用单调队列维护所有可能成为最优解的决策点 jj，即一个决策点 jj 单调递增，数值 aja_j 单调递减的队列。而 fj+max⁡k=j+1iakf_j+\max_{k=j+1}^ia_k 和 aja_j 的单调性却没有关系，所以可以额外维护一个 multiset 来做到和单调队列一起删除，插入元素，每次取第一个迭代器就可以快速转移，时间复杂度 O(nlog⁡n)O(n\log n)。

代码实现

此题代码有很多细节，有些部分借鉴闫总代码，不好理解的结合代码一起看吧：
  1. 如何快速找到第一个不满足 ∑k=j+1iak≤m\sum_{k=j+1}^ia_k\le m 的 jj 呢，二分显然可以。但是双指针可以更快，因为 ii 递增的时候 jj 一定递增，所以我们用一个变量统计总和即可，并且每次及时删除单调队列中不符合的 jj。
  2. fj+max⁡k=j+1iakf_j+\max_{k=j+1}^ia_k 如何快速计算呢，首先利用 ST 表可以完成，但是如果我们仔细挖掘单调队列的性质就会发现某一项的 max⁡k=j+1iak\max_{k=j+1}^ia_k 就是后一项的 aa 值。证明也很简单，不妨假设当前项为 jj ，下一项为 kk ，首先由于单调递减所以 ak=max⁡l=kia_k=\max_{l=k}^{i}，其次由于决策单调递增所以 k>jk>j 且 jj 到 k−1k-1 之间的 aa 值因为比 aka_k 小而被踢出单调队列，所以 fj+max⁡l=j+1ial=fj+akf_j+\max_{l=j+1}^ia_l=f_j+a_k。
  3. 虽然每一个决策 jj 都对应一个 fj+max⁡k=j+1iakf_j+\max_{k=j+1}^ia_k，但是根据第二条可知，每一项的最大值要依赖后一项，也就是说出了单调队列最后一项以外都可以求出对应的 fj+max⁡k=j+1iakf_j+\max_{k=j+1}^ia_k。而最后一项每次都由新插入的 ii 来更新即没插入 ii 前的最后一项在插入 ii 后就变成了倒数第二项可以更新。而此时有人会疑惑 ii 又无法更新，但是这样的担心是不必要的，因为 ii 无法更新 fif_i，而下一轮中若 ii 还存在在单调队列中则会以相同的方式来更新。同理删除元素时第一次删除的即队尾不更新 multiset。
CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+100;
int n,a[N],l=1,r,q[N];
ll m,dp[N],sum;
multiset<ll> st;

void shan(ll x)
{
	if(st.find(x)==st.end()) return;//相当于是在这里判断元素存不存在了
	st.erase(st.find(x));
}

int main()
{
	scanf("%d%lld",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]>m)//不合法的情况
		{
			printf("-1\n");
			return 0;
		}
	}
	for(int i=1,j=0;i<=n;i++)//j就是第一个不满足和小于等于m的位置，详见1
	{
		sum+=a[i];//j+1到i这一段的和
		while(sum>m) sum-=a[++j];
		while(l<=r&&q[l]<j) shan(dp[q[l]]+a[q[l+1]]),l++;//及时排除不合法的决策
		while(l<=r&&a[q[r]]<=a[i]) shan(dp[q[r-1]]+a[q[r]]),r--;//不满足单调性，这里用r-1就是因为最后一项不删，详见3
		if(l<=r) st.insert(dp[q[r]]+a[i]);//队尾用i来更新，详见3
		q[++r]=i;
		dp[i]=dp[j]+a[q[l]];//可能的决策2
		if(st.size()) dp[i]=min(dp[i],*st.begin());//可能的决策1
	}
	printf("%lld\n",dp[n]);
	return 0;
}
完结撒花！！！

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...