题解 P2300 【合并神犇】
3493441984zz
2019-02-24 12:06:26
# 动态规划$+$单调队列优化
------------
看到题解里只有一篇单调队列,而且和我还写的不同,于是发了一篇题解
------------
# 思路:
我们首先看到这个题目后,我们可能会想到贪心合并,每次发现不能构成单调不减序列后,我们就一直合并到能构成单调不减序列
然后就$WA$了$qwq$
例如下面这组数据:
$4,3,3,3,9$
我们到了第一个$3$后,发现不能构成单调不减了,于是我们合并两个$3$,构成:
$4,6,3,9$
再次合并构成:
$4,6,12$
这样的做法错在哪里呢?在于我们没有考虑到一个因素,那就是在相同合并次数下,我们要尽量使得最后一个数尽量小,这样才能保证结果最优,例如相面这组样例,假如我们还是合并两次,但是这次我们先合并$3,3$后,再合并$6,3$,也就是:
$4,6,3,9$
$4,9,9$
我们还是合并了两次,但是我们最后一个数是$9$,比$12$小,后面的序列我们可以填更多的数
于是我们设计状态:
$f[i]$表示前$i$个数合并最小次数
$g[i]$表示前$i$个数保证在合并$f[i]$次的情况下,最后一个数的最小值
------------
先讲$O(n^2)$
转移的话,假如我们在处理$f[i]$
那么我们在$[1,i]$枚举$j$,假如从$j$到$i$这个区间的值的和大于等于$g[j]$,那么就可以转移了(保证单调不减)那么
$$f[i]=f[j]+i-j-1$$
用$sum[i]$表示前缀和
$g[i]=sum[i]-sum[j]$
我们上面讲过$g[i]$越小越好,所以可以用单调队列维护$sum[i]-sum[j]$
------------
虽然好像$O(n^2)$可以过,但是这里给出单调队列优化的代码
下面是美滋滋的代码时间~~~
~~~cpp
#include<iostream>
#include<cstdio>
#define int long long
#define N 200007
using namespace std;
int n,head,tail=1;
int f[N],pre[N],sum[N],q[N];
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;++i)
{
int x;
scanf("%lld",&x);
sum[i]=sum[i-1]+x;
}
for(int i=1;i<=n;++i)
{
while(head+1<tail&&sum[i]>=sum[q[head+1]]+pre[q[head+1]])
++head;
f[i]=f[q[head]]+i-q[head]-1;
pre[i]=sum[i]-sum[q[head]];
while(head<tail&&sum[q[tail-1]]+pre[q[tail-1]]>sum[i]+pre[i])
--tail;
q[tail++]=i;
}
printf("%lld",f[n]);
return 0;
}
~~~