网站建设gzzctyi,网站建设推广好做吗,嗨学网官网,公众号文章存储wordpress题目链接 搜索#xff0c;枚举切的n-1刀。 对于长n宽m要切x刀#xff0c;可以划分为若干个 长n宽m要切x刀 的子问题#xff0c;对所有子问题的答案取max 对所有子问题的方案取min 就是当前状态答案。 这显然是会有很多重复状态的#xff0c;用map记忆化(长宽都是double)。 … 题目链接 搜索枚举切的n-1刀。 对于长n宽m要切x刀可以划分为若干个 长n宽m要切x刀 的子问题对所有子问题的答案取max 对所有子问题的方案取min 就是当前状态答案。 这显然是会有很多重复状态的用map记忆化(长宽都是double)。 每一刀会将当前分成两份。比如当前是横着切枚举上边再切i刀(分成i1份)(下边就再切x-1-i刀)由m不变有 \(n*mn*m*(i1)/(x1)\)可以得到n。同理可以得到每种切法的n,m。 double可以用pairLL.LL表示最简分数不用也没太大问题吧。 总结1.划分子问题记忆化。 2.按切成块数划分面积。(肯定是啊) //824kb 56ms
#include map
#include cstdio
#include algorithm
#define mp std::make_pair
#define pr std::pairdouble,double
//typedef Status std::pairpr,intstd::mappr,double f[10];
std::mappr,double::iterator it;double DFS(double n,double m,int x)
{if(!x) return std::max(n,m)/std::min(n,m);if((itf[x].find(mp(n,m)))!f[x].end()) return it-second;double res1e15, nnn/(x1), mmm/(x1);for(int i0; ix; i)//剩余可切次数为x-1(注意这就是一次) resstd::min(res,std::max(DFS((i1)*nn,m,i),DFS((x-i)*nn,m,x-1-i))),//x是刀数别混了。resstd::min(res,std::max(DFS(n,(i1)*mm,i),DFS(n,(x-i)*mm,x-1-i)));f[x][mp(n,m)]f[x][mp(m,n)]res;return res;
}int main()
{int n,m,x; scanf(%d%d%d,n,m,x);
// double AnsDFS(n,m,x-1);//一样 printf(%.6lf,DFS(n,m,x-1));return 0;
} 转载于:https://www.cnblogs.com/SovietPower/p/8976556.html
