在哪里申请网站域名,重要的建设工程人员查询,十大网站建设排名,购物网站建设 属于信息系统管理与设计么?生日蛋糕
题目大意#xff1a;
一个正方形蛋糕#xff0c;竖着横着各切一刀#xff0c;使他变成四块正方形蛋糕#xff0c;蛋糕中有一些巧克力#xff0c;而小明只能拿巧克力最少的一块#xff0c;请问小明要怎么切才能吃到最多的巧克力
样例输入
8
…#…#…
.##……生日蛋糕
题目大意
一个正方形蛋糕竖着横着各切一刀使他变成四块正方形蛋糕蛋糕中有一些巧克力而小明只能拿巧克力最少的一块请问小明要怎么切才能吃到最多的巧克力
样例输入
8
…#…#…
.##…#…
…#.
.##…
…#.#…
…#.
…
…#…#…
样例输出
3
3 4
数据范围限制
提示
数据说明
20% N50
50% N2000
100% N4500
解题思路
用f[i][j]来表示前i行前j列的巧克力总数那我们就可以得知
f[i][j]f[i−1][j]f[i][j−1]−f[i−1][j−1]sf[i][j]f[i-1][j]f[i][j-1]-f[i-1][j-1]sf[i][j]f[i−1][j]f[i][j−1]−f[i−1][j−1]s
因为f[i-1][j]和f[i][j-1]重复了f[i-1][j-1]所以要减去当此处有巧克力时s为1否则为0
然后我们枚举1,1到n,n的每一个点从这个点开始分割
左上为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]这四个之中最小的就是当前分法的结果再求最大的结果即可
#includecstdio
#includeiostream
#includecstring
#includealgorithm
#includestring
using namespace std;
int n,ans,f[4505][4505],t,x,y;
char c;
int main()
{scanf(%d,n);for (int i1;in;i)for (int j1;jn;j){f[i][j]f[i-1][j]f[i][j-1]-f[i-1][j-1];//求f[i][j]cinc;//输入if(c#) f[i][j];//判断是否有巧克力}for (int i1;in;i)for (int j1;jn;j){tmin(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]));//记录下来if (tans)//判断是否更优{anst;//代替xi;//记录yj;//记录}}printf(%d\n%d %d,ans,x,y);//输出return 0;
}
