给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1而且m>1，m<=n），每段绳子的长度记为k[1],…,k[m]。请问k[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，咱们把它剪成长度分别为二、三、3的三段，此时获得的最大乘积是18。html
由均值不等式得：
n
m
=
k
1
+
k
2
+
⋅
⋅
⋅
+
k
m
m
≥
k
1
k
2
⋅
⋅
⋅
k
m
m
\frac{n}{m} = \frac{k_1 + k_2 + \cdot\cdot\cdot + k_m}{m} \geq \sqrt[m]{k_1k_2 \cdot\cdot\cdot k_m}
m n = m k 1 + k 2 + ⋅ ⋅ ⋅ + k m ≥ m k 1 k 2 ⋅ ⋅ ⋅ k m
web
由上可知，理想状况下，将长度为
n
n
n
m
m
m
n
m
\frac{n}{m}
m n app
咱们设每一段绳子的长度为
x
x
x
f
(
x
)
=
x
n
x
f(x) = x^{\frac{n}{x}}
f ( x ) = x x n
f
(
x
)
f(x)
f ( x )
n
n
n ide
咱们对
f
(
x
)
f(x)
f ( x )
y
=
x
n
x
y = x^{\frac{n}{x}}
y = x x n
ln
y
=
n
x
⋅
ln
x
\ln y = \frac{n}{x} \cdot \ln{x}
ln y = x n ⋅ ln x
d
ln
y
d
x
=
d
ln
y
d
y
⋅
d
y
d
x
=
1
y
⋅
y
′
=
n
⋅
(
−
1
x
2
)
⋅
ln
x
+
n
x
⋅
1
x
=
n
x
2
⋅
(
1
−
ln
x
)
\frac{\mathrm{d}\ln y}{\mathrm{d}x} = \frac{\mathrm{d}\ln y}{\mathrm{d}y} \cdot \frac{\mathrm{d}y}{\mathrm{d}x} = \frac{1}{y} \cdot y^{'} = n \cdot (-\frac{1}{x^2}) \cdot \ln{x} + \frac{n}{x} \cdot \frac{1}{x} = \frac{n}{x^{2}}\cdot(1 - \ln{x})
d x d ln y = d y d ln y ⋅ d x d y = y 1 ⋅ y ′ = n ⋅ ( − x 2 1 ) ⋅ ln x + x n ⋅ x 1 = x 2 n ⋅ ( 1 − ln x )
y
′
=
n
x
2
⋅
(
1
−
ln
x
)
⋅
x
n
x
y^{'} = \frac{n}{x^{2}}\cdot(1 - \ln{x}) \cdot x^{\frac{n}{x}}
y ′ = x 2 n ⋅ ( 1 − ln x ) ⋅ x x n svg
令
y
′
=
0
y^{'} = 0
y ′ = 0
x
=
e
x = e
x = e 函数
又由于
x
x
x
f
(
3
)
>
f
(
2
)
f(3) > f(2)
f ( 3 ) > f ( 2 ) spa
不过这个证实仍是不够严谨，由于咱们没有证实在
x
x
x code
f
(
x
)
=
3
n
3
,
w
h
e
n
n
m
o
d
3
=
0
f(x) = 3^{\frac{n}{3}}, when \; n \; mod \; 3 = 0
f ( x ) = 3 3 n , w h e n n m o d 3 = 0
f
(
x
)
=
4
⋅
3
n
3
−
1
,
w
h
e
n
n
m
o
d
3
=
1
(
因
为
2
×
2
>
1
×
3
)
f(x) = 4 \cdot 3^{\frac{n}{3} - 1}, when \; n \; mod \; 3 = 1 (由于2 \times 2 > 1 \times 3)
f ( x ) = 4 ⋅ 3 3 n − 1 , w h e n n m o d 3 = 1 ( 因 为 2 × 2 > 1 × 3 )
f
(
x
)
=
2
⋅
3
n
3
,
w
h
e
n
n
m
o
d
3
=
2
f(x) = 2 \cdot 3^{\frac{n}{3}}, when \; n \; mod \; 3 = 2
f ( x ) = 2 ⋅ 3 3 n , w h e n n m o d 3 = 2 orm
class Solution {
public :
int cutRope ( int number) {
if ( number == 2 )
return 1 ;
if ( number == 3 )
return 2 ;
if ( number % 3 == 0 )
return ( int ) pow ( 3 , number / 3 ) ;
if ( number % 3 == 1 )
return 4 * ( int ) pow ( 3 , number / 3 - 1 ) ;
if ( number % 3 == 2 )
return 2 * ( int ) pow ( 3 , number / 3 ) ;
}
} ; 运行时间：3msxml