UVA_10970
假设上面就是我们要切的巧克力，橙色的边表示切痕，而且是只有橙色边的位置才会有切痕，如果每条短边都视作一刀的话，那么上面那个巧克力显然要切17刀，这也是最坏的情况了，那么刀数为什么可以比17刀少呢？我们不妨观察红点的位置，如果左右刀痕连在了一起那么可以少一刀，同理如果上下刀痕连一起，也可以少一刀，但是上下和左右的刀痕不能同时连一起。那么也就是说如果有一个红色的这样的点，那么就可以使上下刀痕连一起，或者左右刀痕连一起，从而减少一刀，那么一共有6个这样的点，就可以减少6刀，所以最优就是11刀。
（我的程序是先假设横着切了N-1刀，然后再竖着切(M - 1) * N刀。）
#include<stdio.h> #include<string.h> int main() { int n, m; while(scanf("%d%d", &n, &m) == 2) printf("%d\n", n - 1 + (m - 1) * n); return 0; }