来自 电脑系统 2019-09-27 01:15 的文章
当前位置: 金沙澳门官网网址 > 电脑系统 > 正文

Cake slicing UVA - 1629

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=>>1;15         return d[t][b][l][r]=init+init(m1+1,b,l,r);16     }17     else18     {19         m1=>>1;20         return d[t][b][l][r]=init+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+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+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;42         memset(ans,0x3f,sizeof;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: %dn",++cse,dp(1,n,1,m));57     }58     return 0;59 }

Cake slicing UVA,cakeslicinguva

 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: %dn",++cse,dp(1,n,1,m));
57     }
58     return 0;
59 }

本文由金沙澳门官网网址发布于电脑系统,转载请注明出处:Cake slicing UVA - 1629

关键词: