Cake slicing UVA - 1629

UVA - 1629

ans[t][b][l][r]表示t到b行，l到r列那一块蛋糕切好的最小值
d[t][b][l][r]表示t到b行，l到r列区域的樱桃数，需要预处理

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int d[][][][];

 int ans[][][][];

 int n,m,k,cse;

 int init(int t,int b,int l,int r)

 {

     if(d[t][b][l][r]!=-)    return d[t][b][l][r];

     int m1;

     if(b-t>r-l)

     {

         m1=(t+b)>>;

         return d[t][b][l][r]=init(t,m1,l,r)+init(m1+,b,l,r);

     }

     else

     {

         m1=(l+r)>>;

         return d[t][b][l][r]=init(t,b,l,m1)+init(t,b,m1+,r);

     }

 }

 int dp(int t,int b,int l,int r)

 {

     if(ans[t][b][l][r]!=0x3f3f3f3f)    return ans[t][b][l][r];

     if(d[t][b][l][r]==)    return ans[t][b][l][r]=;

     int i;

     for(i=t;i<b;i++)

         if(d[t][i][l][r]&&d[i+][b][l][r])

             ans[t][b][l][r]=min(ans[t][b][l][r],dp(t,i,l,r)+dp(i+,b,l,r)+r-l+);

     for(i=l;i<r;i++)

         if(d[t][b][l][i]&&d[t][b][i+][r])

             ans[t][b][l][r]=min(ans[t][b][l][r],dp(t,b,l,i)+dp(t,b,i+,r)+b-t+);

     return ans[t][b][l][r];

 }

 int main()

 {

     int i,j,t1,t2,i1,j1;

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

     {

         memset(d,-,sizeof(d));

         memset(ans,0x3f,sizeof(ans));

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

             for(j=;j<=m;j++)

                 d[i][i][j][j]=;

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

         {

             scanf("%d%d",&t1,&t2);

             d[t1][t1][t2][t2]=;

         }

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

             for(j=;j<=m;j++)

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

                     for(j1=j;j1<=m;j1++)

                         init(i,i1,j,j1);

         printf("Case %d: %d\n",++cse,dp(,n,,m));

     }

     return ;

 }