切巧克力如果是1*n
的大小,則最好的切法就是n-1次。若大小為m*n 且 m > 1
,則就是切成m條1*n
的巧克力塊,則先切了m-1次,接著m條1*n
的巧克力塊都要切成1*1
的巧克力塊,則又再切了m*(n-1)
次,總和就是切了(m-1)+(m*(n-1)) = m-1+m*n-m = m*n-1
。則整合一下上述兩種狀況後,可得答案即為m*n-1
。
C++(0.065)
/*******************************************************/
/* UVa 10970 Big Chocolate */
/* Author: Maplewing [at] knightzone.studio */
/* Version: 2014/12/25 */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;
int main(){
int M, N;
while( scanf("%d%d", &M, &N) != EOF ){
printf("%d\n", M*N-1 );
}
return 0;
}