讲序列切割之前，先来个铺垫
高手集训
题目描述：
课程表里有连续的n天可以供你选择，每天都有专题课程。其中第i天的专题趣味程度为h[i]。假设你选择了其中连续的若干天，从第l天到第r天。那么，
训练效果 = h[l]*1 + h[l+1]*2 + ... + h[r]*(r-l+1)
随着训练的深入进行，每天的趣味程度会得到更多倍数的效果。
目前有m种训练方案，每种方案由起始时间和结束时间来描述。请对每种方案输出训练效果。
算法分析
这道题目，我们可以死做，然后就会TLE。为了避免TLE，我们引入一种特殊的前缀和。
其中，s[i]为朴素的前缀和，g[i]为编号加权前缀和。
那么，上面为公式的推导。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=100009;
typedef long long ll;
ll n,m,h[N],s[N],g[N];
void input(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>h[i];
}
}
void BF(){
for(ll i=1;i<=m;i++){
ll l,r;
cin>>l>>r;
ll ans=0;
for(ll j=l;j<=r;++j) ans+=h[j]*(j-l+1);
cout<<ans<<" ";
}
}
void solve(){
for(ll i=1;i<=n;i++){
s[i]=s[i-1]+h[i];
g[i]=g[i-1]+h[i]*i;
}
for(ll i=1;i<=m;++i){
ll l,r;
cin>>l>>r;
ll ans=g[r]-g[l-1]-(s[r]-s[l-1])*(l-1);
cout<<ans<<" ";
}
}
int main(){
freopen("training.in","r",stdin);
freopen("training.out","w",stdout);
input();
if(n<=1000&&m<=1000) BF();
else solve();
return 0;
}这里，我两种算法都放进去了。
防汛指挥
题目描述：
每年夏天，城市的河道都会经历一次汛期的挑战。你作为市长，正在紧锣密鼓的做防汛指挥工作。你所管理的城市有一条中心河道，河道的一侧容易决堤，而这一侧依次排列着n座楼房，编号1到n，其中第i座楼房高度为h[i]。目前你需要将楼房分成若干个相邻连续的区域，由各个区域内部协调防汛资源。若某个连续区域内楼房数量num达到L，则该区域中最矮的 num/L (向下取整) 座楼房会被关闭，其中人员会到区域内其他楼房暂住。若某个连续区域内楼房数量num未到达G，则该区域所有楼房都不可以关闭。通过确定分组管理的方案，本市未关闭的楼房里高度总和最小是多少？
算法分析
首先，这是一道动态规划题。AC动态规划题的心度历程：状态定义→根据样例列表格→找规律→状态转移方程→写代码
定义f[i]表示前i座楼房分组后未关闭的最小高度总和。
给出一组样例：
然后大家列一列表格
/*
f[i]表示前i座楼房分组后未关闭的最小高度总和
n=6,L=3
i=1 ,2 ,3 ,4 ,5, 6
h[i]=2 2 5 4 5 1
f[i]=2 4 7 11 14 15
*/通过找规律，我们发现
于是，我们的状态转移方程也就呼之欲出了
其中rmq()表示求最小值。
代码
/*
f[i]表示前i座楼房分组后未关闭的最小高度总和
n=6,L=3
i=1 ,2 ,3 ,4 ,5, 6
h[i]=2 2 5 4 5 1
f[i]=2 4 7 11 14 15
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=100009;
ll n,L,h[N],bst[N],q[N],f[N],s[N];
void RMQ(){
int l=0,r=0;
for(int i=1;i<=n;i++){
while(l<r&&i-q[l]>=L) l++;
while(l<r&&h[i]<h[q[r-1]]) r--;
q[r++]=i;
bst[i]=h[q[l]];
}
}
int main(){
freopen("flood.in","r",stdin);
freopen("flood.out","w",stdout);
cin>>n>>L;
for(int i=1;i<=n;i++) cin>>h[i];
for(int i=1;i<=n;i++) s[i]=s[i-1]+h[i];
RMQ();
for(int i=1;i<=n;i++){
if(i<L) f[i]=s[i];
else f[i]=min(f[i-1]+h[i],f[i-L]+s[i]-s[i-L]-bst[i]);
}
cout<<f[n]<<endl;
return 0;
}结束
