UVa1629 - Cake slicing

出處：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4504

解題策略：DP

dp[a][b][i][j]表示座標左上角(a,b)到右下角(i,j)的長方形範圍內的最小切割線總長度

0<=a<n, 1<=i<=n, 0<=b<m, 1<=j<=m

cnt[a][b]表示座標左上角(0,0)到右下角(a,b)的櫻桃總數

使用cnt[a][b]計算區間的櫻桃個數，公式如下，櫻桃存在的區間範圍為左開右閉

區間座標左上角(a,b)到右下角(i,j)的櫻桃總數為cnt[i][j]-cnt[a][j]-cnt[i][b]+cnt[a][b]