一、栈的运用

通过活用栈等简单的数据结构，可以巧妙地降低一些算法的复杂度。

POJ 2559

题意：n个宽度为1，高度为h[i]（1<=i<=n）组成的柱形图，求里面包含的长方形的最大面积；

思路：如果确定了长方形的左端点L和右端点R，那么最大可能高度就是min{h[i]|L<=i<R}（一般做题区间都是左闭右开，便于计算），时间复杂度O(n^3)，考虑优化区间最小值，可以降为O(n^2)，但仍然无法在规定时间内求出答案。

考虑换种思路假设面积最大的长方形的左端为L，右端为R，高度为H。如果h[L-1]>=H，那么左端点可以更新为L-1，从而得到更大的长方形，与假设矛盾，故h[L-1]<H。同理，h[R]<H，并且高度H=min{h[i]|L<=i<R}。

做法：我们可以固定h[i]向左右方向延伸，则可以定义两个单调栈：L[i]=(j<=i并且h[j-1]<h[i]的最大的j)   R[i]=(j<i并且h[j]>h[i]的最小的j)

在计算L[i]时，首先，当栈顶的元素j满足h[j]>=h[i]，则不断取出栈顶元素。若栈为空，则L[i]=0，若h[j]<h[i]，则L[i]=j+1.然后把i压入栈中。

时间复杂度：由于栈的压入和弹出操作都是O（n）次，因此整个算法的时间复杂度为O（n）。对于R也可以用同样的方法计算。
#include<cstdio>
typedef long long ll;
const int maxn=100005;
ll a[maxn];
ll st[maxn];
ll l[maxn];
ll r[maxn];
ll max(ll aa,ll bb){
return aa>bb?aa:bb;
}
int main(){
int n;
//  freopen("in9.txt","r",stdin);
while(scanf("%d",&n)!=-1&&n){
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
}
int top=0;
for(int i=0;i<n;i++){
while(top&&a[st[top-1]]>=a[i]){
top--;
}
l[i]=top==0?0:st[top-1]+1;
st[top++]=i;
}
top=0;
for(int i=n-1;i>=0;i--){
while(top&&a[st[top-1]]>=a[i]){
top--;
}
r[i]=top==0?n:st[top-1];
st[top++]=i;
}
ll ans=0;
for(int i=0;i<n;i++){
ans=max(ans,((r[i]-l[i])*a[i]));
}
printf("%lld\n",ans);
}
return 0;
}

二、双端队列的运用

队列是一种只允许在一端删除而在另一端插入的数据结构。双端队列(Deque)是队列的一种拓展，它可以在队列的两端进行插入和删除，它是限定插入和删除操作在表的两端进行的线性表，是一种具有队列和栈的性质的数据结构。

POJ 3709

题意：有一个不递减的序列，现在要把这些数分成若干个部分，每部分不能少于m个数。每部分的权值为所有数减去该部分最小的数的和。求最小的总权值。

首先不难得出，a0是最小的值，为了使操作的次数较小，我们不可能把最小值拿着减。所以我们发现，对于a0这样的较小的项，我们可以选择从小到大来选择需要减少到a0的项。设dpi为只考虑前i项的前提下最少的操作次数，则有dpi=min{dpj+(a[j+1]-a[j])+…+(a[i−1]-a[j])},其中0≤j≤i−k。

直接计算自然没问题，但是O3的复杂度不太好的样子，于是考虑优化：

例如我们记一个前缀和，

Si=a[0]+…+a[i−1]

有dpi=min{dpj+S[i]-S[j+1]-aj*(i-j-1)}
观察方程我们可以发现,若我们设一个函数（用x替换i）fj(x)=−aj∗x+dp[j]−S[j+1]+aj∗(j+1)，则有dp[i]=S[i]+minfj(i),于是计算dp[n]就变为了在i-k+1条直线中寻找x=i的最小值就好了。
于是我们考虑用双端队列去维护所有可能成为最小值的直线的集合，并以从小到大的顺序排列。那么我们如何判断要去掉某条直线呢？

设：

f1(x)=a1∗x+b1
f2(x)=a2∗x+b2
f3(x)=a3∗x+b3

我们有(a2−a1)∗(b3−b2)≥(b2−b1)∗(a3−a2) 时，f2为要排除的直线。

#include<iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include<algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const ll maxn=505000;
ll cas=0;
ll n,k;
ll a[maxn];
ll deq[maxn];//虽然是双端队列但存的是值
ll dp[maxn*10];
ll sh[maxn];//前缀和
bool check(ll f1,llf2,ll f3)
{
ll a1=-a[f1];
ll b1=dp[f1]-sh[f1+1]+a[f1]*(f1+1);
ll a2=-a[f2];
ll b2=dp[f2]-sh[f2+1]+a[f2]*(f2+1);
ll a3=-a[f3];
ll b3=dp[f3]-sh[f3+1]+a[f3]*(f3+1);
return (a2-a1)*(b3-b2)>=(b2-b1)*(a3-a2);
}
ll f(ll j,ll x)
{
return -a[j]*x+dp[j]-sh[j+1]+a[j]*(j+1);
}
int main()
{
//freopen("1.in","r",stdin);
//freopen("2.out","w",stdout);
scanf("%lld",&cas);
for(ll z=0;z<cas;z++)
{
memset(sh,0,sizeof(sh));
memset(a,0,sizeof(a));
memset(dp,0,sizeof(dp));
memset(deq,0,sizeof(deq));
scanf("%lld%lld",&n,&k);
for(ll i=0;i<n;i++)
{
scanf("%lld",&a[i]);
}
for(ll i=0;i<n;i++)
{
sh[i+1]=sh[i]+a[i];
}
ll s=0;
ll t=1;
deq[s]=0;
dp[0]=0;
for(ll i=k;i<=n;i++)
{
if(i-k>=k)
{
while(s+1<t &&check(deq[t-2],deq[t-1],i-k))
{
t--;
}
deq[t]=i-k;
t++;
}
while(s+1<t &&f(deq[s],i)>=f(deq[s+1],i))
{
s++;
}
dp[i]=sh[i]+f(deq[s],i);
}
printf("%lld\n",dp[n]);
}
return 0;
}