【DP】【单调队列】Codeforces1131G Most Dangerous Shark

题意：

给出一排多米诺骨牌各自的高度，以及推到它的代价。

推到既可以向左也可以向右。

求全部推到的最小代价。

输入格式较为恶心

分析：

比赛中是真没时间去做了。
读题读了20min…（主要是输入格式）

首先，有一个很显然的DP
$d{p}_i$表示前i个骨牌全部推到的最小代价。
那么有2种转移方式：
假设把i向左推，能倒的最远的一个骨牌编号为j。
$d{p}_i=d{p}_{j?1}+cos{t}_i$
S为一骨牌集合，其中的每个骨牌均满足：在i左边，且将其向右推能推倒i
dpi=min{dpSk?1+costSk}dp_i=min\{dp_{S_k-1}+cost_{S_k}\}dpi?=min{ dpSk??1?+costSk??}

裸做是$O(N^2)$

考虑优化
有一个很显然的性质：
假设$i$向右推，能倒的最远的位置为$j$
如果满足$j\ge i+1$，那么将$i+1$向右推，能倒的最远位置一定不超过$j$
因为i能推倒i+1，所以i+1倒了能推倒的位置i就一定能推倒。

有了这个性质，就可以用单调栈来维护集合S（即在i某侧，并能推倒i的集合）。

加入一个新位置$i^{\prime }$后，检查队首元素能否直接推倒$i^{\prime }$

然后做两遍单调栈，第二次维护一下栈的前缀最小值即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define SF scanf
#define PF printf
#define MAXM 10000010
#define MAXN 250010
using namespace std;
typedef long long ll;
int n,m;
vector<int> pri[MAXN],he[MAXN];
ll p[MAXM];
int st[MAXM],top,h[MAXM],tot,lft[MAXM];
ll minv[MAXM],dp[MAXM];
int main(){
    SF("%d%d",&n,&m);for(int i=1;i<=n;i++){
    SF("%d",&tot);he[i].resize(tot);pri[i].resize(tot);for(int j=0;j<tot;j++)SF("%d",&he[i][j]);	for(int j=0;j<tot;j++)SF("%d",&pri[i][j]);}ll mul;int q,id;SF("%d",&q);int cnt=0;for(int i=1;i<=q;i++){
    SF("%d%lld",&id,&mul);	for(int j=0;j<int(he[id].size());j++){
    h[++cnt]=he[id][j];p[cnt]=1ll*pri[id][j]*mul;}}for(int i=m;i>=1;i--){
    while(top>0&&i<=st[top]-h[st[top]]){
    lft[st[top]]=i+1;top--;}st[++top]=i;}while(top>0){
    lft[st[top]]=1;top--;	}for(int i=1;i<=m;i++){
    while(top>0&&i>=st[top]+h[st[top]])top--;dp[i]=dp[lft[i]-1]+p[i];if(top>0)dp[i]=min(dp[i],minv[top]);st[++top]=i;minv[top]=dp[i-1]+p[i];if(top>1)minv[top]=min(minv[top],minv[top-1]);}PF("%lld",dp[m]);
}