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;

}

巴特西

Codeforces1131G Most Dangerous Shark

Description

Original Problem

Chinese Translation

Solution

Code

最新文章

热门文章