首页 > > 程序设计 > C/C++ >

Cake slicing UVA - 1629

2018-06-17 22:04:03来源：未知阅读 ()

UVA - 1629

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

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int d[21][21][21][21];
 6 int ans[21][21][21][21];
 7 int n,m,k,cse;
 8 int init(int t,int b,int l,int r)
 9 {
10     if(d[t][b][l][r]!=-1)    return d[t][b][l][r];
11     int m1;
12     if(b-t>r-l)
13     {
14         m1=(t+b)>>1;
15         return d[t][b][l][r]=init(t,m1,l,r)+init(m1+1,b,l,r);
16     }
17     else
18     {
19         m1=(l+r)>>1;
20         return d[t][b][l][r]=init(t,b,l,m1)+init(t,b,m1+1,r);
21     }
22 }
23 int dp(int t,int b,int l,int r)
24 {
25     if(ans[t][b][l][r]!=0x3f3f3f3f)    return ans[t][b][l][r];
26     if(d[t][b][l][r]==1)    return ans[t][b][l][r]=0;
27     int i;
28     for(i=t;i<b;i++)
29         if(d[t][i][l][r]&&d[i+1][b][l][r])
30             ans[t][b][l][r]=min(ans[t][b][l][r],dp(t,i,l,r)+dp(i+1,b,l,r)+r-l+1);
31     for(i=l;i<r;i++)
32         if(d[t][b][l][i]&&d[t][b][i+1][r])
33             ans[t][b][l][r]=min(ans[t][b][l][r],dp(t,b,l,i)+dp(t,b,i+1,r)+b-t+1);
34     return ans[t][b][l][r];
35 }
36 int main()
37 {
38     int i,j,t1,t2,i1,j1;
39     while(scanf("%d%d%d",&n,&m,&k)==3)
40     {
41         memset(d,-1,sizeof(d));
42         memset(ans,0x3f,sizeof(ans));
43         for(i=1;i<=n;i++)
44             for(j=1;j<=m;j++)
45                 d[i][i][j][j]=0;
46         for(i=1;i<=k;i++)
47         {
48             scanf("%d%d",&t1,&t2);
49             d[t1][t1][t2][t2]=1;
50         }
51         for(i=1;i<=n;i++)
52             for(j=1;j<=m;j++)
53                 for(i1=i;i1<=n;i1++)
54                     for(j1=j;j1<=m;j1++)
55                         init(i,i1,j,j1);
56         printf("Case %d: %d\n",++cse,dp(1,n,1,m));
57     }
58     return 0;
59 }