题目概述

有 $n$ 个骨牌，每个骨牌有高度和推倒代价，骨牌可以往左往右推倒，如果两个骨牌的距离小于推倒骨牌高度那么就会向同一个方向倒下，求最小代价使得所有骨牌都倒下。

解题报告

不难想到 $O(n^2)$ DP，就是对于每个骨牌，考虑往左推倒或者往右推倒：

$$ f_i=min\{min\{f_{j-1}+c_j|r_j\ge i\},f_{l_i-1}+c_i\} $$

其中 $l_i,r_i$ 表示 $i$ 往左往右能够到达的地方，可以 $O(n)$ 单调栈求出。

我们需要优化这个DP，由于从 $f_{l_i-1}$ 转移是 $O(1)$ 的，所以我们需要优化的部分是骨牌向右推的情况，考虑骨牌向右推的性质：如果向右推倒骨牌 $i$ 会导致骨牌 $j(j>i)$ 被推倒，且 $f_j\ge f_i$ ，那么 $j$ 肯定没有用了。

所以这可以用单调栈优化，维护一个递减的单调栈，每次先把 $r_j<i$ 的 $j$ 弹出栈，取出栈顶修正 $f_i$ ，然后看 $f_i$ 能否加入栈中就行了。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxm=250000,maxn=10000000;

int m,n,te,K[maxm+5],a[maxm+5],b[maxm+5],h[maxn+5],l[maxn+5],r[maxn+5];
LL c[maxn+5],f[maxn+5];int top,stk[maxn+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
#define F(x) (f[(x)-1]+c[x])
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    readi(m);readi(n);n=0;
    for (int i=1;i<=m;i++){
        readi(K[i]);K[i]+=K[i-1];
        for (int j=K[i-1]+1;j<=K[i];j++) readi(a[j]);
        for (int j=K[i-1]+1;j<=K[i];j++) readi(b[j]);
    }
    for (readi(te);te;te--){
        int ID,x;readi(ID);readi(x);
        for (int i=K[ID-1]+1;i<=K[ID];i++) h[++n]=a[i],c[n]=(LL)b[i]*x;
    }
    for (int i=(top=0,1);i<=n;i++){
        l[i]=i;while (top&&i-stk[top]<h[i]) l[i]=l[stk[top--]];
        while (top&&l[stk[top]]>l[i]) top--;stk[++top]=i;
    }
    for (int i=(top=0,n);i;i--){
        r[i]=i;while (top&&stk[top]-i<h[i]) r[i]=r[stk[top--]];
        while (top&&r[stk[top]]<r[i]) top--;stk[++top]=i;
    }
    for (int i=1;i<=n;i++){
        f[i]=f[l[i]-1]+c[i];while (top&&r[stk[top]]<i) top--;
        if (top) f[i]=min(f[i],F(stk[top]));
        if (!top||F(stk[top])>F(i)) stk[++top]=i;
    }printf("%lld\n",f[n]);return 0;
}