[HOJ] 267 - Raisins

Problem : 267 - Raisins

Problem：

邦妮，普洛的夫著名的巧克力製造商，需要將一整塊含有葡萄乾的巧克力進行切割。巧克力塊是一個由許多大小相等的正方形切片所組成的矩形。這些切片和巧克力的邊界對其，且排列在N列M欄上，因此共有N*M個切片。每一個切片上有一個或更多個葡萄乾，且沒有葡萄乾會位於兩個切片之間或橫跨兩個切片。



剛開始時，巧克力是一個單一完整的區塊，邦妮需要將他切成越來越小的區塊，直到他將整個巧克力切割成N*M個切片為止。由於邦妮非常的忙碌，他需要他的助手，史萊彼得，幫忙切割的工作。彼得只進行直線，且終端到終端的切割，同時他希望每一次切割後都能獲得報酬。由於邦妮手上沒有錢，所以他提議用葡萄乾作為彼得的報酬。史萊彼得同意了這項安排，但必須滿足下列的條件：每次他將一個區塊的巧克力切割成兩個較小的區塊時，他所得到的報酬，必須和原有區塊上面葡萄乾的數目相同。

邦妮希望付給彼得越少的報酬越好。他知道每一個切片上有多少個葡萄乾。他可以決定將區塊交給彼得切割的順序，並且可以告訴彼得如何切割(水平或垂直)，以及在何處切割。請幫助邦妮決定如何將巧克力塊切隔成個別的切片，且付給彼得的葡萄乾數越少越好。

Input：

第一行有兩個整數N和M(1 ≤ N,M ≤ 50)。

接下來有N行，每行M個數。第i+1行的第j個數就是題目描述中的第i行第j欄個切片上的葡萄乾樹木，每個數字皆為正整數且不超過1000。

Output：

輸出一個數字表示最小花費。

Sample Input：

2 3
2 7 5
1 9 5

Sample Output：

77

HINT：

---------------------------------------------------------------------------------------------------
#include<stdio.h>
#define cnt(a,b,c,d) (add[c][d]-add[a-1][d]-add[c][b-1]+add[a-1][b-1])
int s[55][55],add[55][55]={0},v[55][55][55][55]={0};
long long int ans(int a,int b,int c,int d){
    if(a==c && b==d) return 0;
    if(v[a][b][c][d]) return v[a][b][c][d];
    long long int p=99999999999999LL,k;
    int i;
    for(i=a;i<c;i++){
        k=ans(a,b,i,d)+ans(i+1,b,c,d);
        if(k<p) p=k;
    }
    for(i=b;i<d;i++){
        k=ans(a,b,c,i)+ans(a,i+1,c,d);
        if(k<p) p=k;
    }
    v[a][b][c][d]=cnt(a,b,c,d)+p;
    return v[a][b][c][d];
}
int main(){
    int n,m,i,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++){
            scanf("%d",&s[i][j]);
            add[i][j]=s[i][j]+add[i-1][j]+add[i][j-1]-add[i-1][j-1];
        }
    printf("%lld\n",ans(1,1,n,m));
}