HDU 2513 Cake slicing

#include<bits/stdc++.h>

using namespace std;

int n,m,k;

int cherry[405],dp[405][405];

int solve(int l,int r)

{

    //printf("%d,%d %d,%d\n",l/m,l%m,r/m,r%m);

    int &ret=dp[l][r];

    if(ret!=-1)return ret;

    int nmin=30,nmax=-1,mmin=30,mmax=-1;

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

    {

        int ntmp=cherry[i]/m,mtmp=cherry[i]%m;

        if(ntmp>=l/m&&ntmp<=r/m&&mtmp>=l%m&&mtmp<=r%m)nmin=min(nmin,ntmp),nmax=max(nmax,ntmp),mmin=min(mmin,mtmp),mmax=max(mmax,mtmp);

    }

    if(nmin==-1)ret=0;

    if(nmin==nmax&&mmin==mmax)ret=0;

    if(ret==0)return ret;

    ret=0x3f3f3f3f;

    for(int i=nmin;i<nmax;++i)ret=min(ret,solve(l,r-(r/m-i)*m)+solve(l+(i-l/m+1)*m,r)+(r%m-l%m+1));

    for(int i=mmin;i<mmax;++i)ret=min(ret,solve(l,r-(r%m-i))+solve(l+(i-l%m+1),r)+(r/m-l/m+1));

    return ret;

}

int main()

{

    int Case=0;

    while(~scanf("%d%d%d",&n,&m,&k))

    {

        memset(dp,-1,sizeof dp);

        for(int i=1;i<=k;++i){int a,b;scanf("%d%d",&a,&b);cherry[i]=a*m-m+b-1;}

        printf("Case %d: %d\n",++Case,solve(0,n*m-1));

    }

}
巴特西

HDU 2513 Cake slicing

最新文章

热门文章
