Codeforces1131G Most Dangerous Shark

• 2020 年 9 月 17 日
• 筆記
• DP, 数据结构

Description

Original Problem

Chinese Translation

大概就是给你一个间隔为1的多米诺序列，推倒一个多米诺骨牌有个花费，求推倒所有多米诺骨牌的最小花费

Solution

这道题先处理出每一个点最左及最右可推倒的位置，这可以用栈维护
设以上位置为\(l_{i}\),\(r_{i}\)
接下来设\(f_{i}\)为第1~i个点全部倒下，且第i个点往左倒的最小花费
\(g_{i}\)为第1~i个点全部倒下，且第i个点往右倒的最小花费
先考虑\(f_{i}\)
显然，\(f_{i}=min(f_{l_{i}-1},g_{l_{i}-1})+cost_{i}\)
即第\(l_{i}-1\)之前的点都倒下再加上\(l_{i}\)到i倒下的花费
再考虑\(g_{i}\)
对于\(g_{i}\)，初始肯定是手动放倒该点即$$g_{i}=min(g_{i-1},f_{i-1})+cost_{i}$$
用一个栈维护最小的能推倒i的\(g_{j}\)来更新\(g_{i}\)
因为j能影响i，那么i能影响的j都能影响，所以只有\(g_{i}<g_{j}\)时才需要将该点压入栈中

Code

#include <cstdio>
#include <algorithm>
#define M 10000001
#define N 250010
#define open(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
int n,m,i,q,id,mul,t,j,cnt,zhan[M],left[M],right[M],k[N],a[N],b[N],h[M],pl[N];
long long f[M],g[M],c[M];
int main()
{
    open("shark");
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++)
    {
        scanf("%d",&k[i]);
        pl[i]=cnt+1;
        for (j=1;j<=k[i];j++)
            scanf("%d",&a[++cnt]);
        cnt=pl[i]-1;
        for (j=1;j<=k[i];j++)
            scanf("%d",&b[++cnt]);
    }
    pl[n+1]=cnt+1;
    scanf("%d",&q);
    for (i=1;i<=q;i++)
    {
        scanf("%d %d",&id,&mul);
        for (j=pl[id];j<=pl[id+1]-1;j++)
        {
            h[++t]=a[j];
            c[t]=(long long)b[j]*mul;
        }
    }zhan[1]=zhan[0]=1;
    for (i=1;i<=m;i++)
    {
        left[i]=max(1,i-h[i]+1);
        t=left[i];
        while (left[i]<=zhan[zhan[0]])
        {
            if (!zhan[0]) break;
            t=min(t,left[zhan[zhan[0]]]);
            zhan[0]--;
        }
        left[i]=t;
        zhan[++zhan[0]]=i;
    }
    zhan[1]=m;zhan[0]=1;
    for (i=m;i>=1;i--)
    {
        right[i]=min(m,i+h[i]-1);
        t=right[i];
        while (right[i]>=zhan[zhan[0]])
        {
            if (!zhan[0]) break;
            t=max(t,right[zhan[zhan[0]]]);
            zhan[0]--;
        }
        right[i]=t;
        zhan[++zhan[0]]=i;
    }
    f[1]=g[1]=c[1];
    zhan[0]=zhan[1]=1;
    for (i=2;i<=m;i++)
    {
        f[i]=min(f[left[i]-1],g[left[i]-1])+c[i];
        while (right[zhan[zhan[0]]]<i && zhan[0]) zhan[0]--;
        g[i]=min(g[i-1],f[i-1])+c[i];
        if (!zhan[0]) zhan[++zhan[0]]=i;else 
        {
            g[i]=min(g[i],g[zhan[zhan[0]]]);
            if (g[i]<g[zhan[zhan[0]]]) zhan[++zhan[0]]=i;
        }
    }
    printf("%lld",min(g[m],f[m]));
    return 0;
}