Topcoder SRM 654 DIV1 500 FoldingPaper2 递归 + 枚举

题意：给你一张长W，宽H 的纸，问你能不能者成给定的大小，每一次折纸只能折成整数大小。
解题思路：递推+枚举枚举给定大小的长和宽，然后套进 W，H中求最小值，折纸策略最优是每次折半。
解题代码：
  1 // BEGIN CUT HERE
  2 /*
  3 
  4 */
  5 // END CUT HERE
  6 #line 7 "FoldingPaper2.cpp"
  7 #include <cstdlib>
  8 #include <cctype>
  9 #include <cstring>
 10 #include <cstdio>
 11 #include <cmath>
 12 #include <algorithm>
 13 #include <vector>
 14 #include <string>
 15 #include <iostream>
 16 #include <sstream>
 17 #include <map>
 18 #include <set>
 19 #include <queue>
 20 #include <stack>
 21 #include <fstream>
 22 #include <numeric>
 23 #include <iomanip>
 24 #include <bitset>
 25 #include <list>
 26 #include <stdexcept>
 27 #include <functional>
 28 #include <utility>
 29 #include <ctime>
 30 using namespace std;
 31 
 32 #define PB push_back
 33 #define MP make_pair
 34 
 35 #define REP(i,n) for(i=0;i<(n);++i)
 36 #define FOR(i,l,h) for(i=(l);i<=(h);++i)
 37 #define FORD(i,h,l) for(i=(h);i>=(l);--i)
 38 
 39 typedef vector<int> VI;
 40 typedef vector<string> VS;
 41 typedef vector<double> VD;
 42 typedef long long LL;
 43 typedef pair<int,int> PII;
 44 
 45 int find(int now,int val)
 46 {
 47     if(now == val)
 48         return 0 ; 
 49     if(val > now/2)
 50         return 1;
 51     if(now % 2 == 0 )
 52         return 1 + find(now/2,val);
 53     return 1 + find(now/2+1,val);
 54 }
 55 class FoldingPaper2
 56 {
 57         public:
 58         int solve(int W,int  H, int A)
 59         {
 60             int mi = 1e9; 
 61             int ok = 0 ; 
 62             for(int i = 1; i <= sqrt(A) + 1;i ++)
 63             {
 64                 if(A % i == 0 )
 65                 {
 66                   if(i <= W && A/i <= H)
 67                   {
 68                   mi = min(find(W,i)+find(H,A/i),mi);
 69                   ok = 1; 
 70                   }
 71                   if(i <= H && A/i <= W)
 72                   {
 73                   mi = min(find(H,i)+find(W,A/i),mi);
 74                   ok = 1; 
 75                   }
 76                 }
 77             }
 78             if(ok)
 79             return mi ;
 80             else return -1; 
 81 
 82         }
 83         
 84 // BEGIN CUT HERE
 85     public:
 86     void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); }
 87     private:
 88     template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '"' << *iter << "","; os << " }"; return os.str(); }
 89     void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "	Expected: "" << Expected << '"' << endl; cerr << "	Received: "" << Received << '"' << endl; } }
 90     void test_case_0() { int Arg0 = 5; int Arg1 = 3; int Arg2 = 12; int Arg3 = 1; verify_case(0, Arg3, solve(Arg0, Arg1, Arg2)); }
 91     void test_case_1() { int Arg0 = 2; int Arg1 = 2; int Arg2 = 3; int Arg3 = -1; verify_case(1, Arg3, solve(Arg0, Arg1, Arg2)); }
 92     void test_case_2() { int Arg0 = 4; int Arg1 = 4; int Arg2 = 1; int Arg3 = 4; verify_case(2, Arg3, solve(Arg0, Arg1, Arg2)); }
 93     void test_case_3() { int Arg0 = 127; int Arg1 = 129; int Arg2 = 72; int Arg3 = 8; verify_case(3, Arg3, solve(Arg0, Arg1, Arg2)); }
 94     void test_case_4() { int Arg0 = 1; int Arg1 = 100000; int Arg2 = 100000; int Arg3 = 0; verify_case(4, Arg3, solve(Arg0, Arg1, Arg2)); }
 95     void test_case_5() { int Arg0 = 1; int Arg1 = 1; int Arg2 = 2; int Arg3 = -1; verify_case(5, Arg3, solve(Arg0, Arg1, Arg2)); }
 96 
 97 // END CUT HERE
 98 
 99 };
100 
101 // BEGIN CUT HERE
102 int main()
103 {
104         FoldingPaper2 ___test;
105         ___test.run_test(-1);
106         return 0;
107 }
108 // END CUT HERE
View Code