Warning: session_start(): open(/tmp/sess_de43411744c148c119ee8365c88bc934, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/4/43994124a9168f34c03db2ff7cd35d94.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
**格式**：max 使用 \max，sum 使用 \text{sum}，代码使用 '''' 隐藏，均已修改。学会使用 ''\begin{cases}\end{cases}'' 来表示不同的 case，不需要自己设计格式。
**内容**：内容过于简单！可尝试从读者的角度想想能否看懂。
- 动态转移方程 -> 状态转移方程
- $(1\le j k
\end{cases}
$$
答案为 $\text{ans}=\max\{dp[i]\}$。
但是时间复杂度为 $O(nk)$，显然会超时。
注意到 $\text{sum}[i]$ 可以直接提出，即 $dp[i]=\max\{dp[j]\}+\text{sum}[i]$，所以我们只需用一个单调队列来维护 $dp[i]$ 的最值，复杂度可以降低为 $O(n)$。
#include
#include
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]
==== 练习 ====
[[https://www.luogu.com.cn/problem/solution/P3957|洛谷p3957]]