Educational Codeforces Round 1 E. Chocolate Bar（记忆化搜索）

本文主要是介绍Educational Codeforces Round 1 E. Chocolate Bar（记忆化搜索），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接
题意：在n*m的矩形切出面积是k
解法：记忆化搜索

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define X first
#define Y second
#define cl(a,b) memset(a,b,sizeof(a))
typedef pair<int,int> P;
const int maxn=100005;
const LL inf=1<<27;
const LL mod=1e9+7;
LL dp[35][35][55];
LL dfs(int n,int m,int k){//printf("n = %d, m = %d, k = %d\n",n,m,k);if(k==0||m*n==k)return 0;if(dp[n][m][k]!=-1)return dp[n][m][k];LL ans=inf;for(int i=1;i<n;i++){for(int j=0;j<=k;j++){ans=min(ans,dfs(i,m,j)+dfs(n-i,m,k-j)+(LL)m*m);}}for(int i=1;i<m;i++){for(int j=0;j<=k;j++){ans=min(ans,dfs(n,i,j)+dfs(n,m-i,k-j)+(LL)n*n);}}return dp[n][m][k]=ans;
}int main(){int T;scanf("%d",&T);cl(dp,-1);while(T--){int n,m,k;scanf("%d%d%d",&n,&m,&k);printf("%lld\n",dfs(n,m,k));}return 0;
}

这篇关于Educational Codeforces Round 1 E. Chocolate Bar（记忆化搜索）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---