题解 P2300 【合并神犇】

3493441984zz

2019-02-24 12:06:26

Solution

# 动态规划$+$单调队列优化 ------------ 看到题解里只有一篇单调队列,而且和我还写的不同,于是发了一篇题解 ------------ # 思路: 我们首先看到这个题目后,我们可能会想到贪心合并,每次发现不能构成单调不减序列后,我们就一直合并到能构成单调不减序列 然后就$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; } ~~~