CF598E Chocolate Bar

1. CF598E Chocolate Bar

       一道简单的DP，虽然用搜索写的。我们用f(i,j,z)表示把X×Y的巧克力分成总大小为Z的小块所需最小代价。每次掰开的方式有两种，横着掰和竖着掰，故有两种转移。

#include<bits/stdc++.h>
using namespace std;
int n,m,k,T;
const int inf=0x3f3f3f3f;
typedef long long ll;
int a[53][53][75];
int f(int x,int y,int z){
    if(!z||x*y==z) return 0;
    if(a[x][y][z]) return a[x][y][z];
    int res=inf;
    for(int i=1;i<=y-i;i++){
        for(int j=0;j<=z;j++){
            res=std::min(res,x*x+f(x,i,j)+f(x,y-i,z-j));
        }
    }
    for(int i=1;i<=x-i;i++){
        for(int j=0;j<=z;j++){
            res=std::min(res,y*y+f(i,y,j)+f(x-i,y,z-j));
        }
    }


    return a[x][y][z]=res;
}
int main(){
    cin>>T;
    while(T--){
        scanf("%d%d%d",&n,&m,&k);
        printf("%d\n",f(n,m,k));
    }
    return 0;
}