本文主要是介绍【Educational Codeforces Round 1E】【动态规划-多维DP】Chocolate Bar 矩形巧克力掰开吃的最小成本，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<math.h>
#include<iostream>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre(){freopen("c://test//input.in","r",stdin);freopen("c://test//output.out","w",stdout);}
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1,class T2>inline void gmax(T1 &a,T2 b){if(b>a)a=b;}
template <class T1,class T2>inline void gmin(T1 &a,T2 b){if(b<a)a=b;}
const int N=0,M=0,Z=1e9+7,ms63=1061109567;
int casenum,casei;
int f[32][32][52];
void DP()
{//初始化MS(f,63);for(int i=0;i<=30;i++){for(int j=0;j<=30;j++)f[i][j][0]=0;}for(int i=1;i<=30;i++){for(int j=1;j<=30;j++)if(i*j<=50)f[i][j][i*j]=0;}//状态转移for(int i=1;i<=30;i++){for(int j=1;j<=30;j++){int top=min(i*j,50);for(int k=1;k<=top;k++)//总共要切的份数{for(int u=1;u<=i/2;u++)//横着切{int topp=min(u*j,k);for(int kk=0;kk<=topp;kk++){gmin(f[i][j][k],f[u][j][kk]+f[i-u][j][k-kk]+j*j);}}for(int v=1;v<=j/2;v++)//竖着切{int topp=min(v*i,k);for(int kk=0;kk<=topp;kk++){gmin(f[i][j][k],f[i][v][kk]+f[i][j-v][k-kk]+i*i);}}}}}
}
int main()
{DP();int n,m,k;scanf("%d",&casenum);for(casei=1;casei<=casenum;casei++){scanf("%d%d%d",&n,&m,&k);printf("%d\n",f[n][m][k]);}return 0;
}
/*
【trick&&吐槽】
1，不要让自己太懒惰呀，这道水题就是差1分钟AC >_<
2，没有AC的原因是我把数组给爆了！初始化的边界问题也要多多注意呀！RE时返回的可能并不是RE【题意】
有T（4e4）组询问。
对于每组询问，问你，我们想要在一个n（30）*m（30）的大巧克力中，
吃掉一个大小为k（1<=k<=min(n*m,50)）的小巧克力的最小体力成本。吃巧克力为什么需要体力成本呢？
因为如果巧克力太大了，我们就要把它掰开。
对于一个i*j的巧克力，我们可以横着沿[1,i-1]的线掰开，也可以纵着沿[1,j-1]的线掰开。
横着掰开的成本是掰开巧克力的宽度，也就是j；纵着掰开的成本是掰开巧克力的长度，也就是i。【类型】
DP【分析】
我们直接枚举
1，大巧克力的长
2，大巧克力的宽
3，吃巧克力的大小
4，横着还是竖着切，在哪里切
5，一侧吃的巧克力的大小
6，另一侧吃的巧克力的大小
这道题就做完啦
时间复杂度为O(n*m*k*(n+m)*k)
大概为30*30*50*60*50=1.35e8
AC完全没有压力！这样就AC啦！具体来说——
就是定义f[i][j][k]表示我们在一个i*j的巧克力块中吃一个大小恰好为k的巧克力的成本
数组大小为[31][31][51]
初始化f[i][j][0]=f[i][j][i*j] 注意i*j可能达到900，然而我们数组才开到50，于是这里要特判下。
做CF的时候我就是因为这里的错误没有做到AC >_<
状态转移方程为——
gamx(f[i][j][k],f[u][j][kk]+f[i-u][j][k-kk]+j*j);u∈[1,j/2],u表示横着切的位置，我们只需要枚举小的那一半即可，成本自然是j*j
gamx(f[i][j][k],f[i][v][kk]+f[i][j-v][k-kk]+i*i);v∈[1,i/2],v表示竖着切的位置，我们只需要枚举小的的一半即可，成本自然是i*i
kk表示在这一半吃的巧克力的数量，显然kk∈[0,min(u*j,k)]或kk∈[0,min(i*v,k)];
这样更新一下，我们永远是先更新小的矩阵，再更新大的矩形。后效性一定有保证。每个状态都得到了更新。于是最后直接输出f[n][m][k]即可。【时间复杂度&&优化】
O(n*m*k*(n+m)*k)【数据】
10 10 9*/这篇关于【Educational Codeforces Round 1E】【动态规划-多维DP】Chocolate Bar 矩形巧克力掰开吃的最小成本的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
