/*

题目：

	给定一个长度为n的绳子，把绳子剪为m段，(n>1,m>1)

	求各段绳子乘积的最大值。

*/

/*

思路：

	贪婪算法。

	当绳子的长度大于5时，尽可能多的剪长度为3的绳子；当剩下的绳子长度为4时，把绳子剪为两段长度为2的绳子。

*/

/*

证明：

	当n>=5时，2(n-2)>n,3(n-3)>n,也就是当n大于5时，就把它剪为长度为3或2的绳子，且3(n-3)>2(n-2),所以尽可能的剪为长度为3的绳子。

	当n=4时，剪为2*2最大。

*/

#include<iostream>

#include<string.h>

#include<algorithm>

#include<math.h>

using namespace std;

int cutRope(int number){

    if(number <= 1){

        throw("invalid parameter");

    }

    if(number == 2 || number == 3){

        return number-1;

    }

    int timesOf3 = number / 3;

	//当剩余长度为4时，剪为2*2

    if(number - timesOf3 * 3 == 1){

        timesOf3 --;

    }

    int timesOf2 = (number - timesOf3 * 3) / 2;

    return (int)(pow(3,timesOf3))*(int)(pow(2,timesOf2));

}

int main(){

    cout<<cutRope(8)<<endl;

}