[2019HDU多校第一场][HDU 6580][C. Milk]

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6580

题目大意：\(n\times m\)大小的方格上有\(k\)瓶水，喝完每瓶水都需要一定的时间。初始点在\((1,1)\)，每次可以向左或者向右走一步，如果当前的纵坐标为\(\frac{m+1}{2}\)则可以向下走一步。对所有的\(i \in [1,k]\)，求喝恰好\(i\)瓶水需要花费的时间。\(n,m\leq 10^9, k\leq 10^4\)

题解：首先对瓶子的横坐标离散化处理，一行一行地更新答案。每到新的一行，先预处理出向左（右）走喝了\(i\)瓶水后，回到原点以及不回到原点所需要的最短时间，分别记为\(l,r,l\_back,r\_back\)。然后将左右两边合并，求出喝了\(i\)瓶水后，回到或不回到原点所需时间，记为\(g,g\_back\)。设\(f[i]\)为从\((1,1)\)出发，喝了\(i\)瓶水后回到当前行中点所需的最短时间，则这时就可以根据\(g\)来和之前的\(f[i]\)来更新答案，并用\(g\_back\)来更新\(f\)的值。时间复杂度为\(O(k^2)\)

　　　对于每一行\(l,r,l\_back,r\_back\)数组的预处理，可以考虑先对喝水所需时间进行排序，枚举最远走到哪里。当最远到达的点确定后，就可以只考虑喝水所需要的时间来更新状态了

　　　具体实现见代码，注意如果当前行为\(1\)时要特殊处理

#include<bits/stdc++.h>

using namespace std;

#define N 10005

#define LL long long

#define MP make_pair

LL T,n,m,k,f[N],ans[N];

LL l[N],l_back[N],r[N],r_back[N],g[N];

LL g_back[N],nxt[N];

pair<LL,LL>cost[N];

map<LL,vector<pair<LL,LL>>>mp;

void init()

{

    mp.clear();

    scanf("%lld%lld%lld",&n,&m,&k);

    for(int i=;i<=k;i++)

      f[i]=ans[i]=1e18;

    for(int i=;i<=k;i++)

      {

      LL R,c,t;

      scanf("%lld%lld%lld",&R,&c,&t);

      mp[R].push_back(MP(c,t));

      }

    f[]=ans[]=m->>;

    LL lst=,mx=;

    for(const auto &pi:mp)

      {

      LL R=pi.first;

      auto d=pi.second;

      d.push_back(MP(,));

      sort(d.begin(),d.end());

      LL n=d.size()-,cnt=,mid=m+>>;

      for(int i=;i<=n;i++)

        if(d[i].first<mid)cnt++;

      d[].first=mid;

      if(R==)//对当前行为1的特判

        {

        nxt[]=;

        for(int i=;i<=n;i++)

          nxt[i]=i+,r[i]=r_back[i]=1e18;

        for(int i=;i<=n;i++)

          cost[i]=MP(d[i].second,i);

        sort(cost+,cost+n+);

        for(int i=n;i>=;i--)

          {

          LL sum=,id=;

          for(int j=nxt[],k=;j<=n;j=nxt[j],k++)

            {

            sum+=cost[j].first;

            r[k]=min(r[k],sum+d[i].first-);

            if(nxt[j]<=n && cost[nxt[j]].second==i)id=j;

            r_back[k]=min(r_back[k],sum+*max(d[i].first,mid)-mid-);

            }

          nxt[id]=nxt[nxt[id]];

          }

        for(int i=;i<=n;i++)

          {

          ans[i]=min(ans[i],r[i]);

          f[i]=min(f[i],r_back[i]);

          }

        mx=n;

        continue;

        }

      nxt[]=;

      for(int i=;i<=cnt;i++)

        {

        cost[i]=MP(d[i].second,i);

        l[i]=l_back[i]=1e18;

        nxt[i]=i+;

        }

      sort(cost+,cost+cnt+);//对喝水耗时进行排序

      for(int i=;i<=cnt;i++)//枚举最远走到哪，从远到近枚举

        {

        LL sum=,id=;

        for(int j=nxt[],k=;j<=cnt;j=nxt[j],k++)//取前k小的喝水耗时，更新答案

          {

          sum+=cost[j].first;

          l[k]=min(l[k],sum+mid-d[i].first);

          if(nxt[j]<=cnt && cost[nxt[j]].second==i)id=j;

          l_back[k]=min(l_back[k],sum+*(mid-d[i].first));

          }

        nxt[id]=nxt[nxt[id]];//删除当前最远点

        }

      nxt[cnt]=cnt+;

      for(int i=cnt+;i<=n;i++)

        {

        cost[i]=MP(d[i].second,i);

        r[i-cnt]=r_back[i-cnt]=1e18;

        nxt[i]=i+;

        }

      sort(cost+cnt+,cost+n+);

      for(int i=n;i>cnt;i--)

        {

        LL sum=,id=cnt;

        for(int j=nxt[cnt],k=;j<=n;j=nxt[j],k++)

          {

          sum+=cost[j].first;

          r[k]=min(r[k],sum+d[i].first-mid);

          if(nxt[j]<=n && cost[nxt[j]].second==i)id=j;

          r_back[k]=min(r_back[k],sum+*(d[i].first-mid));

          }

        nxt[id]=nxt[nxt[id]];

        }

      for(int i=;i<=n;i++)//合并l, r

        {

        g[i]=g_back[i]=1e18;

        for(int j=max(0ll,i-(n-cnt));j<=min(1ll*i,cnt);j++)

          {

          g[i]=min(g[i],min(l[j]+r_back[i-j],l_back[j]+r[i-j]));

          g_back[i]=min(g_back[i],min(l_back[j]+r_back[i-j],l_back[j]+r_back[i-j]));

          }

        }

      for(int i=;i<=mx;i++)//更新ans

        {

        f[i]+=R-lst;//先加上走过的行数

        for(int j=;j<=n;j++)

          ans[i+j]=min(ans[i+j],f[i]+g[j]);

        }

      for(int i=mx;i>=;i--)//更新f

        for(int j=n;j>=;j--)

          f[i+j]=min(f[i+j],f[i]+g_back[j]);

      mx+=n,lst=R;//更新上一次走到的行数

      }

    for(int i=;i<=k;i++)

      printf("%lld%c",ans[i],i<k?' ':'\n');

}

int main()

{

    scanf("%lld",&T);

    while(T--)init();

}

巴特西

[2019HDU多校第一场][HDU 6580][C. Milk]

最新文章

热门文章