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