本文主要是介绍【记忆化搜索】【DFS】Chocolate,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
Charlie 有一块巧克力。
这块巧克力是矩形的,有 n 行 m 列一共 n × m 个大小相同的小块,每一小块都有一个美味值 ai,j。
Charlie 有 k 个朋友,他希望把巧克力分给这些朋友。
Charlie 按如下方法分配巧克力:做 k-1 次分割,每次拿出一块巧克力,将它
沿水平或竖直方向分成两块矩形的巧克力。分割完成后一共有 k 块巧克力,Charlie
会把这 k 块巧克力一一分给他的朋友们。
一块巧克力的美味值定义为它的所有小块的美味值之和。Charlie 想知道是否
存在一种可行的方案,使每个朋友获得的巧克力的美味值相等。
输入
本题有多组测试数据。第一行一个正整数 T 表示数据组数。
对于每组测试数据:
第一行 3 个正整数表示 n, m, k。
接下来 n 行,每行 m 个正整数,表示每一小块的美味值
输出
对于每个测试数据,输出一行 YES 或 NO,表示是否存在可行方案。
输入样例
2
1 3 2
2 1 1
2 2 3
2 3
3 1
输出样例
YES
NO
思路
记忆化搜索
详见代码
#include<Iostream>
#include<Cstring>
#include<Cstdio>
using namespace std;
bool Bol[30][30][30][30];
bool B[30][30][30][30];
int F[30][30][30][30];
int A[30][30];
int T,Sum;
int n,m,k;
bool Dfs(int r,int c,int x,int y)
这篇关于【记忆化搜索】【DFS】Chocolate的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!