bzoj1024题解

【解题思路】
　　爆搜，状态f(r,x,y)表示剩下r刀，边长为x和y，对于每个状态枚举切成两块后的长度比或宽度比。复杂度o((n/2)ⁿ)。
【参考代码】
 #include <algorithm>

 #include <cstdio>

 #define REP(I,start,end) for(int I=(start);I<=(end);I++)

 #define PER(I,start,end) for(int I=(start);I>=(end);I--)

 #define REPs(I,start,end,step) for(int I=(start);I<=(end);I+=(step))

 #define PERs(I,start,end,step) for(int I=(start);I>=(end);I-=(step))

 #define maxint 32767

 #define maxlongint 2147483647

 #define maxint64 9223372036854775807ll

 using namespace std;

 typedef unsigned short US;

 typedef unsigned long UL;

 typedef long long LL;

 typedef unsigned long long ULL;

 inline int getint()

 {

     char ch=getchar();

     while((ch<''||ch>'')&&ch!='-')

         ch=getchar();

     int result=;

     bool impositive=ch=='-';

     if(impositive)

         ch=getchar();

     while(ch>=''&&ch<='')

     {

         result=(result<<)+(result<<)+ch-'';

         ch=getchar();

     }

     return impositive?-result:result;

 }

 inline int putint(int n)

 {

     int result=;

     char* sav=new char[];

     bool impositive=n<;

     if(impositive)

     {

         putchar('-');

         n=-n;

     }

     sav[]=n%+'';

     while(n/=)

         sav[result++]=n%+'';

     PER(i,result-,)

         putchar(sav[i]);

     delete []sav;

     return result+impositive;

 }

 inline LL getLL()

 {

     char ch=getchar();

     while((ch<''||ch>'')&&ch!='-')

         ch=getchar();

     LL result=0ll;

     bool impositive=ch=='-';

     if(impositive)

         ch=getchar();

     while(ch>=''&&ch<='')

     {

         result=(result<<)+(result<<)+ch-'';

         ch=getchar();

     }

     return impositive?-result:result;

 }

 inline int putLL(LL n)

 {

     int result=;

     char* sav=new char[];

     bool impositive=n<;

     if(impositive)

     {

         putchar('-');

         n=-n;

     }

     sav[]=n%+'';

     while(n/=)

         sav[result++]=n%+'';

     PER(i,result-,)

         putchar(sav[i]);

     delete []sav;

     return result+impositive;

 }

 template<typename integer> inline int read_int(integer &n)

 {

     char ch=getchar();

     while((ch<''||ch>'')&&ch!='-')

         ch=getchar();

     int result=n=integer();

     bool impositive=ch=='-';

     if(impositive)

         ch=getchar();

     while(ch>=''&&ch<='')

     {

         n=(n<<)+(n<<)+integer(ch-'');

         result++;

         ch=getchar();

     }

     if(impositive)

     {

         n=-n;

         result++;

     }

     return result;

 }

 template<typename integer> inline int write_int(integer n)

 {

     int result=;

     char* sav=new char[];

     bool impositive=n<;

     if(impositive)

     {

         putchar('-');

         n=-n;

     }

     sav[]=n%+'';

     while(n/=)

         sav[result++]=n%+'';

     PER(i,result-,)

         putchar(sav[i]);

     delete []sav;

     return result+impositive;

 }

 template<typename T> inline bool getmin(T &target,T pattern)

 {

     bool can=pattern<target;

     if(can)

         target=pattern;

     return can;

 }

 template<typename T> inline bool getmax(T &target,T pattern)

 {

     bool can=pattern>target;

     if(can)

         target=pattern;

     return can;

 }

 //==========================================Header Template================================================

 #include <iomanip>

 #include <iostream>

 double DFS(int rest,double _x,double _y)

 {

     if(rest==)

         return _x>_y?_x/_y:_y/_x;

     double result=maxlongint;

     REP(i,,rest>>)

     {

         long double x0=_x/rest,y0=_y/rest,_r=rest-i;

         getmin(result,min(max(DFS(i,x0*i,_y),DFS(_r,x0*_r,_y)),max(DFS(i,_x,y0*i),DFS(_r,_x,y0*_r))));

     }

     return result;

 }

 int main()

 {

     int x=getint(),y=getint(),n=getint();

     cout<<setiosflags(ios::fixed)<<setprecision()<<DFS(n,x,y)<<endl;

     return ;

 }
巴特西

bzoj1024题解

最新文章

热门文章
