程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> Usaco*Brownie Slicing

Usaco*Brownie Slicing

編輯:關於C++

Usaco*Brownie Slicing。本站提示廣大學習愛好者:(Usaco*Brownie Slicing)文章只能為提供參考,不一定能成為您想要的結果。以下是Usaco*Brownie Slicing正文


Description

Bessie烘焙了一塊巧克力蛋糕。這塊蛋糕是由R*C(1 <= R,C <= 500)個小的巧克力蛋糕組成的。 第i行,第j列的蛋糕有N_ij(1 <= N_ij <= 4,000)塊巧克力碎屑。 Bessie想把蛋糕分紅A*B塊,(1 <= A <= R,1 <= B <= C): 給A*B只奶牛。蛋糕先程度地切A-1刀 (只能切沿整數坐標切)來把蛋糕劃分紅A塊。然後再把剩上去的每一塊獨立地切B-1刀, 也只能切沿整數坐標切。其他A*B-1只奶牛就每人選一塊,留下一塊給Bessie。由於貪婪, 他們只會留給Bessie巧克力碎屑最少的那塊。 求出Bessie最優狀況下會取得多少巧克力碎屑。 例如,思索一個5*4的蛋糕,下面的碎屑散布如下圖所示: 1 2 2 1 3 1 1 1 2 0 1 3 1 1 1 1 1 1 1 1 Bessie必需把蛋糕切成4條,每條分紅2塊。Bessie能像這樣切蛋糕: 1 2 | 2 1 --------- 3 | 1 1 1 --------- 2 0 1 | 3 --------- 1 1 | 1 1 1 1 | 1 1 因而,其他得寸進尺的牛拿完後,Bessie仍可以拿走3個巧克力碎屑。

Input

* 第1行: 四個空格隔開的數: R, C, A ,B * 第2-R+1行: 第i+1行有C個整數, N_i1 , N_i2 .. N_iC

Output

* 第1行: 一個整數: Bessie保證能拿到的最多碎屑數

Sample Input

5 4 4 2
1 2 2 1
3 1 1 1
2 0 1 3
1 1 1 1
1 1 1 1

Sample Output

3     二分答案,貪婪判別以如今的值為答案能否切成a*b塊。
 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 int a[501][501]={0};
 5 int r,c,a1,b1;
 6 
 7 bool check(int now)//判別以後答案的正確性
 8 {
 9     int tot=0,x=0,y=0,j=0,i=0,lasti=0;
10     while (i<r)//i為訪問到第幾行,防止越界
11     {
12         ++i;
13         j=0;
14         y=0;//以後(lasti~i這一塊面包被豎著切成y塊面包)
15         while ((j<c)&&(y<b1))
16         {
17             tot=0;
18             while ((tot<now)&&(j<c))//應用貪婪,一列一列加
19             {
20                 ++j;
21                 for (int i2=lasti+1;i2<=i;++i2)
22                   tot=tot+a[i2][j];
23             }
24             if (tot>=now)//假如可以發生一塊新的面包,則將y+1
25               ++y;
26         }
27         if (y>=b1)//當lasti~i行的面包能被切成大於等於B(b1)塊且每一塊的碎屑都大於mid,x+1,開端枚舉下一次該切在哪
28         {
29             ++x;
30             lasti=i;
31         }
32     }34     if (x>=a1)
35       return true;
36     return false;
37 }
38 
39 int main()
40 {
41     cin>>r>>c>>a1>>b1;
42     int right=0;
43     for (int i=1;i<=r;++i)
44       for (int j=1;j<=c;++j)
45       {
46           cin>>a[i][j];
47           right+=a[i][j];
48       }
49     int ans=0,left=0,mid=0;
50     while (left<=right)//二分答案
51     {
52         mid=(left+right)/2;
53         if (check(mid)==true)
54         {
55           left=mid+1;
56           ans=mid;//防止呈現死循環
57         }
58         else right=mid-1;
59     }
60     cout<<ans<<endl;
61     return 0;
62 }

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved