生日蛋糕

題目大意：

一個(gè)正方形蛋糕，豎著橫著各切一刀，使他變成四塊正方形蛋糕，蛋糕中有一些巧克力，而小明只能拿巧克力最少的一塊，請(qǐng)問(wèn)小明要怎么切才能吃到最多的巧克力

樣例輸入

8

…#…#…

.##…#…

…#.

.##…

…#.#…

…#.

…

…#…#…

樣例輸出

3

3 4

數(shù)據(jù)范圍限制

提示

數(shù)據(jù)說(shuō)明：

20% N<=50

50% N<=2000

100% N<=4500

解題思路：

用f[i][j]來(lái)表示前i行前j列的巧克力總數(shù)，那我們就可以得知：

$$f[i][j]=f[i?1][j]+f[i][j?1]?f[i?1][j?1]+s$$

因?yàn)閒[i-1][j]和f[i][j-1]重復(fù)了f[i-1][j-1]所以要減去，當(dāng)此處有巧克力時(shí)，s為1否則為0

然后我們枚舉1,1到n,n的每一個(gè)點(diǎn)，從這個(gè)點(diǎn)開(kāi)始分割

左上為f[i][j]，右上為f[i][n]-f[i][j]，左下為f[n][j]-f[i][j]，右下為f[n][n]-f[i][n]-f[n][j]+f[i][j]，這四個(gè)之中最小的就是當(dāng)前分法的結(jié)果，再求最大的結(jié)果，即可

#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<string> using namespace std; int n,ans,f[4505][4505],t,x,y; char c; int main() {scanf("%d",&n);for (int i=1;i<=n;i++)for (int j=1;j<=n;j++){f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1];//求f[i][j]cin>>c;//輸入if(c=='#') f[i][j]++;//判斷是否有巧克力}for (int i=1;i<=n;i++)for (int j=1;j<=n;j++){t=min(min(f[i][j],f[i][n]-f[i][j]),min(f[n][j]-f[i][j],f[n][n]-f[i][n]-f[n][j]+f[i][j]));//記錄下來(lái)if (t>=ans)//判斷是否更優(yōu){ans=t;//代替x=i;//記錄y=j;//記錄}}printf("%d\n%d %d",ans,x,y);//輸出return 0; }

總結(jié)

以上是生活随笔為你收集整理的【模拟】生日蛋糕（jzoj 1613）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。