DP真的不会想|洛谷 P1714 切蛋糕（dp+RMQ）
传送门
首先，很简单的dp方程：
fi=max(si?sj)(j∈[i?m,i])
然后发现 si与 j无关，可以提出来：
fi=si?min(sj)(j∈[i?m,i])
发现这个方程可以用数据结构优化，比如线段树，树状数组等等，我这里推荐用st表。
预处理： O(nlogn)递推： O(n)
代码： 【DP真的不会想|洛谷 P1714 切蛋糕（dp+RMQ）】
#include
#define ll long long
using namespace std;
inline int read(){
int x=0;
char ch=' ';
int f=1;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')f=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
int n,m;
int a[500001];
int s[500001];
int st[20][500001];
inline int query(int l,int r){
int k=log(r-l+1)/log(2);
return min(st[k][l],st[k][r-(1<>1]+1;
}
n=read();
m=read();
for(int i=1;
i<=n;
i++){
a[i]=read();
s[i]=s[i-1]+a[i];
st[0][i]=s[i];
}
for(int k=1;
k<=19;
++k){
for(int i=1;
i+(1< 推荐阅读
- 急于表达——往往欲速则不达
- 2018-02-06第三天|2018-02-06第三天 不能再了，反思到位就差改变
- 家乡的那条小河
- 一个人的碎碎念
- 赠己诗
- 这辈子我们都不要再联系了
- 死结。
- 我从来不做坏事
- 时间老了
- 我错了，余生不再打扰