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;
}