題目鏈接
搜索，枚舉切的n-1刀。
對于長n寬m要切x刀，可以劃分為若干個 長n'寬m'要切x'刀 的子問題，對所有子問題的答案取max 對所有子問題的方案取min 就是當前狀態答案。
這顯然是會有很多重復狀態的，用map記憶化(長寬都是double)。
每一刀會將當前分成兩份。比如當前是橫著切，枚舉上邊再切i刀(分成i+1份)(下邊就再切x-1-i刀)，由m不變，有 \(n'*m=n*m*(i+1)/(x+1)\)，可以得到n'。同理可以得到每種切法的n',m'。
double可以用pair<LL.LL>表示最簡分數，不用也沒太大問題吧。
總結：1.劃分子問題；記憶化。
2.按切成塊數劃分面積。(肯定是啊)
//824kb 56ms
#include <map>
#include <cstdio>
#include <algorithm>
#define mp std::make_pair
#define pr std::pair<double,double>
//typedef Status std::pair<pr,int>std::map<pr,double> f[10];
std::map<pr,double>::iterator it;double DFS(double n,double m,int x)
{if(!x) return std::max(n,m)/std::min(n,m);if((it=f[x].find(mp(n,m)))!=f[x].end()) return it->second;double res=1e15, nn=n/(x+1), mm=m/(x+1);for(int i=0; i<x; ++i)//剩余可切次數為x-1(注意這就是一次) res=std::min(res,std::max(DFS((i+1)*nn,m,i),DFS((x-i)*nn,m,x-1-i))),//x是刀數，別混了。res=std::min(res,std::max(DFS(n,(i+1)*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 Ans=DFS(n,m,x-1);//一樣 printf("%.6lf",DFS(n,m,x-1));return 0;
}
