2020-2021:teams:legal_string:qgjyf2001
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:qgjyf2001 [2020/05/06 16:05] qgjyf2001 |
2020-2021:teams:legal_string:qgjyf2001 [2020/08/07 14:26] (当前版本) qgjyf2001 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ====== dp的优化 ====== | + | [[2020-2021:teams:legal_string:front_page|back]] |
| - | ===== 一、单调队列优化 ===== | + | ====== 我太菜了 ====== |
| - | 单调队列优化，可以降低诸如$dp[i]=max\{dp[j]\}+C[i](1\le j <i)$这样的动态转移方程的时间复杂度。主要的原理就是利用一个单调队列来维护$dp[i]$的最值。 | + | ===== 专题 ===== |
| + | [[2020-2021:teams:legal_string:dp的优化]] | ||
| - | ==== 一道例题 ==== | + | [[可持久化线段树]] |
| - | [[https://www.luogu.com.cn/problem/P2627|洛谷p2627]] | + | [[DFT]] |
| - | 我们不难写出动态转移方程$dp[i]=\left\{\begin{aligned} sum[i],i\le k\\max\{dp[j-1]+sum[i]-sum[j]\}(i-k \le j\le i,i>k)\end{aligned}\right.$ | + | [[计算几何]] |
| - | 答案为$ans=max\{dp[i]\}$ | + | [[BSGS]] |
| - | 但是时间复杂度为$O(nk)$，显然会超时 | + | [[Polya定理]] |
| - | 注意到$sum[i]$可以直接提出，即$dp[i]=max\{dp[j]\}+sum[i]$，所以我们只需用一个单调队列来维护$dp[i]$的最值，复杂度可以降低为$O(n)$ | + | [[半平面交]] |
| - | 代码 | + | ===== 题解 ===== |
| - | + | [[Cf639 Div1 A、B ]] | |
| - | <code cpp> | + | |
| - | #include <stdio.h> | + | |
| - | #include <iostream> | + | |
| - | using namespace std; | + | |
| - | int n,k; | + | |
| - | long long e[100001]; | + | |
| - | long long dp[100001]; | + | |
| - | long long sum[100001]; | + | |
| - | int q[100001]; | + | |
| - | int front=0,tail=1; | + | |
| - | long long a(int now) | + | |
| - | { | + | |
| - | return dp[now-1]-sum[now]; | + | |
| - | } | + | |
| - | int main() | + | |
| - | { | + | |
| - | scanf("%d %d",&n,&k); | + | |
| - | int rec=0; | + | |
| - | for (int i=1;i<=n;i++) | + | |
| - | { | + | |
| - | scanf("%lld",&e[i]); | + | |
| - | sum[i]=sum[i-1]+e[i]; | + | |
| - | } | + | |
| - | for (int i=1;i<=n;i++) | + | |
| - | { | + | |
| - | while (front<=tail&&q[front]<i-k) | + | |
| - | front++; | + | |
| - | dp[i]=a(q[front])+sum[i]; | + | |
| - | while (front<=tail&&a(q[tail])<=a(i)) | + | |
| - | tail--; | + | |
| - | q[++tail]=i; | + | |
| - | } | + | |
| - | long long ans=0; | + | |
| - | for (int i=1;i<=n;i++) | + | |
| - | ans=max(ans,dp[i]); | + | |
| - | printf("%lld",ans); | + | |
| - | return 0; | + | |
| - | } | + | |
| - | </code> | + | |
| - | ==== 练习 ==== | + | |
| - | + | ||
| - | [[https://www.luogu.com.cn/problem/solution/P3957|洛谷p3957]] | + | |
| + | [[Cf641]] | ||
| + | [[Cf643]] | ||
2020-2021/teams/legal_string/qgjyf2001.1588752336.txt.gz · 最后更改: 2020/05/06 16:05 由 qgjyf2001
